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
15764 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

1 2 3 2 5 6 7 8 3 find the next term in the series

3 Answers Virtusa,

how to reuse an outdated laptop?

0 Answers

Why am i appreciated?

1 Answers

please provide me the type of questions or question pattern of bally.

0 Answers

Write a regular expression for "Capgemini Services Pvt.Ltd"

0 Answers Cap Gemini,

why IT?

0 Answers

friends help me..am a btech fresher.. wt is the eligibility criteria for TCS???? like %...repli me clearly from x onwards..

0 Answers

CSS corp interview process and placement papers

0 Answers CSS Corp,

What do you think determines a person's progress in a good company?

0 Answers

W.A.P to take input of an array and display the entered no. in dos.

0 Answers NHPC,

How many of 14 digit numbers we can make with 1,2,3,4,5 that are divisible by 4. Repetitions allowed.

0 Answers

what does the interviewer mean by saying "have a good life " cheerfully at the end of an HR interview??? is this positive or negative sign to be selected?

0 Answers

For more Engineering AllOther Interview Questions Click Here