Interested to Buy Any Domain ? << Click Here >> for more details...
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;
}
:
- 2 Answers
- 15639 Views
- I also Faced
- E-Mail Answers
Answer Posted / 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 |
Post New Answer View All Answers
how do we get persistent databases?
Difference between software process model and software process.?
i want a richdatatable to be displayed only when a list has some value in the bean, and a datatable with header only if the list is empty. And i want the datatable to be printed only when ajax button is clicked??
WHAT IS THE MEANING OF FLASHING VD AND FD INSTALLATION PLENIUM BOXES IN CENTRAL AIR CONDITION
Differences between Java and C++? which is faster?
what do you mean by a p-code?
hai,am a marine engineer..pls anyone tell me what is the abbrevation for "gfca" in Mitsui B&w 7l67gfca engine.my mail id is kamaraj_mech@yahoo.co.in
Please. Does someone know how to inicialize tapes in ATL? I need have 100 tapes to init inside the ATL, how is the process to complete this request?
what size shaft is required to transmit 100 hp @1000 RPM ,if max shear stress is 10,000 PSI,angle of twist must be less than 1' /ft/shaft is made of steel.
Given two strings, find the sub-string of the first string having minimum length which is having all the characters in second string
If i update, insert or delete records in my view will it affect my base table?????
why do you want to join tcs
How we calculate steam turbine governor linkage assembly?
requirement:To move display statements in a cobol program to a dataset.These display statements were not in main program but in calling program and we were not allowed to move these info via sysout dd dsn='dataset.name' . please let me know the ways this can be handled
what is the work of Loopback ?
