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
- 15738 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
hi i am avinash ,i am doing ma b-tech(cse) final year and i have been detained for 2years due to attendance and i will be finished ma b-tech in 6 years ,plz tell me weather i will be eligible for government jobs like bhel, drdo,or any other private companies
please send aptitude test papers for reference with answers
plz plz help me "how can i face dell varcent round"....? plzzzzzzzz help me friends.....?
write a programe to print this string in reverse order and find out how many times letter c is repeated? string = { c was desined by dennis ritchie}. also find out the lenth of the string.
give me some knowledge about automation on which asked on interview
i am shortlisted in corporation bank for the post of computer officer the next phase is group discussion. i want to know how to prepare and what about the topics for preparing thanking you if you have any suggestion please give me prabhatmishra21@rediffmail.com
what is difference between shell commands and shell scripting commands or both r same?
I am student pursuing B.E/B.tech in Computers 8'th sem.What should i do for a better carrier.Plz suggest other than programming languages.Is the ERP a better one to do?plz help...
write a c program which accept input as:Anu.B.Kapur and give out as:Kapur.A.B using pointers
WAP in Java to print the format AMIT M I T
I have failed my intermediate can i write entrance exam the next year after completing my backlogs
A rectangular beam section of 300 mm width and 500 mm effective depth is reinforced with 4 bars of 20 mm diameter, what shear reinforcement is required to resist 200 kN shear (use working stress method)?
Guys! I coplted 10th with 80% and +2 with 64% now am dng c.s.e b.tech...i want to go abroad for higher studies i want to write tofel...plZ GIVE UR SUGGESTIONS!
how can i write a program in c of SPARCE MATRIX(data structure)?
I am having 17 months experience in development.I want to take testing as my career.I dont have experience in testing. Will get job anywhere?
