What is the time complexity T(n) of the nested loops
below? For simplicity, you may assume that n is a power of
2. That is, n = 2k for some positive integer k.
:
i = n;
while (i >= 1){
j = i;
while (j <= n) {
<body of the inner while loop > //
Needs &#61553;(1).
j = 2 * j;
}
i = &#61675;i/2&#61691;;
}
:

Answers were Sorted based on User's Feedback



What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n..

Answer / arefe

hello I'm not sure about what I'm going to say . please tell me if you think it's wrong.
at first let's write some steps of it .
1) i = j = n
2) i = n/2 , j = n/2 --> j = n
3) i = n/4 , j = n/4 --> j = n/2 --> j = n
4) i = n/8 , j = n/8 --> j = n/4 --> j = n/2 , j = n
.
.
.
now if we count ,
the number of n , which j is equal to is log(n) ,
the number of n/2 , which j is equal to is log(n)-1 ,
the number of n/4 , which j is equal to is log(n)-2 ,
the number of n/8 , which j is equal to is log(n)-3 ,
and so on ,
so the result is summation log(n) - i , which i is from 0 to log(n) ,
we write log(n) out of Sigma and multiple it with log(n) + 1,( if we write Sigma term we have log(n) +1 , log(n))
and summation i , which i is from 0 to log(n) , is equal to (log(n)+1)(log(n))/2

Is This Answer Correct ?    0 Yes 0 No

What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n..

Answer / muhammad ijaz khan

The outer loop divides the working area in half in each
iteration. So the running time of this algorithm is
proportional to the number of times n can be divided by 2.
The inner loop will be executed unlimitted time. So
the time complexity of the outer loop will be the function
of ln and the total time is: T(n)= n*ln n

Is This Answer Correct ?    10 Yes 20 No

Post New Answer

More Engineering AllOther Interview Questions

searching a B-tree indexed tree compared to B+ tree is slow..True or false

0 Answers   NIC,


if all user defined constructor of a class made private,can we create an object of that class?justify your answer with an example.

2 Answers  


int i=~0; uint j=(uint)i; j++; printf(“%d”,j); what is the use of "uint" int the above code

0 Answers   Microsoft,


in which website , i can able to get the electrical basics.?????????????

0 Answers  


what is the work of Loopback ?

0 Answers  






Some question are asked from computers also. How we calculate sum in Excel? can we find cube root in Excel if yes , how? If i want to send excel sheet to 10 different person, how i can send it ( don`t tell me by mailing) condition given by interviewer.If A=.03rs(tsqr), value of r increase by 50%, s by 30% & t decrease by 20%. find value of A. If two coins having dia 25 & 16 they are rotate in their axis , Coin having dia 25 reach a point at x per sec, in how many min coin having dia 16 reach that place, Both are rotating in same direction.

0 Answers   NTPC,


which of the following is not a storage class specifier in c?

1 Answers   Infosys,


what is the print server

1 Answers  


What is the difference between while & do while loop

0 Answers  


What is the reason of hunting of variable turbine geometry?

2 Answers  


What do you mean by static routing and dynamic routing?

10 Answers   IBM, Microsoft,


What do you mean by client /server for a post scarcity world

0 Answers  


Categories
  • Civil Engineering Interview Questions Civil Engineering (5085)
  • Mechanical Engineering Interview Questions Mechanical Engineering (4451)
  • Electrical Engineering Interview Questions Electrical Engineering (16632)
  • Electronics Communications Interview Questions Electronics Communications (3918)
  • Chemical Engineering Interview Questions Chemical Engineering (1095)
  • Aeronautical Engineering Interview Questions Aeronautical Engineering (239)
  • Bio Engineering Interview Questions Bio Engineering (96)
  • Metallurgy Interview Questions Metallurgy (361)
  • Industrial Engineering Interview Questions Industrial Engineering (259)
  • Instrumentation Interview Questions Instrumentation (3014)
  • Automobile Engineering Interview Questions Automobile Engineering (332)
  • Mechatronics Engineering Interview Questions Mechatronics Engineering (97)
  • Marine Engineering Interview Questions Marine Engineering (124)
  • Power Plant Engineering Interview Questions Power Plant Engineering (172)
  • Textile Engineering Interview Questions Textile Engineering (575)
  • Production Engineering Interview Questions Production Engineering (25)
  • Satellite Systems Engineering Interview Questions Satellite Systems Engineering (106)
  • Engineering AllOther Interview Questions Engineering AllOther (1379)