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
- 15777 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
create a C program, the .exe file of that program run system will reboot any one help me
What are the inspection and test plan for lift materials?
i need the placement paper of ford IT service...
Write a program to count the no. of occurrence of word in given string Ex- Ram is good boy. Ram is doing good job. Ram – 2 is – 2 good – 2 boy – 1 doing –1 job – 1
What is Campus selection process of patni at Adcet,Ashta at 24th dec 2010.Also give apti syllabus.
discus the worst and best case complexity of binary search
Write a program to maintain a singly linked list having the following functions: a) Creation of the list b) Displaying the list. c) Swap all nodes at consecutive even odd positions. E.g.: The nodes at position 1 should be swapped with node 2, node 3 with node 4 and so on.
what is different between static block and public static void main??
what is a structure in c language?
sir ,,kindly provide me 10 year old solved question papers of gate ,i am from CS. branch...
what are the advantages as disadvantages of the V-model?
hi , anyone plz end nic model papers to my id
explain software engineering practices
I am selected interview for computer sc.please give me some information how many types question asked in interview.my id is sumanadas10@gmail.com
how is the config take place and from reciever side how will process the data into internal table
