What is the time complexity T(n) of the nested loops below? For simplicity, y

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;
}
:

Question Posted / lucky

2 Answers
15737 Views
I also Faced
E-Mail Answers

Answers were Sorted based on User's Feedback

What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n..

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

What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n..

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

Post New Answer

More Engineering AllOther Interview Questions

how to find out the name of the users who are currently working starting with the same characters in unix os

0 Answers

why view is created in database

0 Answers Daraz.pk,

what is your experience in developing technical specifications?

0 Answers

plz explain abt refrigeration r22 bitzer comprassors trouble shooting and maintenance

0 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

0 Answers

What is the actual procedure of charging synthetic oil if the machine is under positive refrigerant pressure.

0 Answers

how can i write a program in c of SPARCE MATRIX(data structure)?

0 Answers

i am going to give interview for the post of ibps po..so there is a question in my mind which is "Being an electonics and communication engineer how can you help in banks, I mean whats the application of your education in banking."

0 Answers IBPS,

searching a B-tree indexed tree compared to B+ tree is slow..True or false

0 Answers NIC,

write a program to reverse a string using recursive function without using str functions.

0 Answers

how much the percentile as a good percentile in elitmus.

0 Answers

how to create user name stape by stape in cisco router {with command}

0 Answers

For more Engineering AllOther Interview Questions Click Here