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 (1).
j = 2 * j;
}
i = i/2;
}
:
Answers were Sorted based on User's Feedback
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 |
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 |
searching a B-tree indexed tree compared to B+ tree is slow..True or false
if all user defined constructor of a class made private,can we create an object of that class?justify your answer with an example.
int i=~0; uint j=(uint)i; j++; printf(“%d”,j); what is the use of "uint" int the above code
in which website , i can able to get the electrical basics.?????????????
what is the work of Loopback ?
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.
which of the following is not a storage class specifier in c?
what is the print server
What is the difference between while & do while loop
What is the reason of hunting of variable turbine geometry?
What do you mean by static routing and dynamic routing?
What do you mean by client /server for a post scarcity world