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
- 15691 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 to increase the chiller effiency?
how convert the spiral model to prototype model ?
What are the inspection and test plan for lift materials?
how the parting surface is selected in injection mould
Can one be shocked holding a wire carrying a very large current with a low voltage source?
What is Moore's law and what limits the size of a computer chip?
when air is supplied from larger diameter pipe with some pressure if change diameter to small pipe the pressure increases or not? also what is increased pressureor velocity?
whether we can implement VPN based on UDP? If yes then tell how? If no tell why not?
Can have i call constructor in interface?
What is the difference between operator overloading and function overloading in C when compared with C++?
i need NIC written test paper or give me any idea about written exam.Plz send me at smileever8@gmail.com
What is the difference between "type testing" and "product qualification"?
who is the judge in case of the auditor has raised an NCR against an auditee? who should decide weather this NCR is acceptable and the auditee has to accept?
find the salary of an employee where employee number is known
how to cable size by Amp with example
