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

Why am i appreciated?

1 Answers

what is putchar() and getchar()?????

1 Answers

could i know the selection pattern at hpcl, am an undergradute in chemical technology, but my sujects or course do not figure out antwhere on the lists.

0 Answers

Why it is a preferable option in parallelextender development ?

0 Answers

Why does the 'divisibility by 3' rule work?

0 Answers

describe how your code can determine if the user entered an input box value or click the cancel button?

0 Answers

WHAT ARE THE ADVANTAGE OF SYSTEM ENGINEER

0 Answers

explain in detail about life cycle of thread

0 Answers

what is the heat insulation material is adaptable for a flue gas duct that carries waste heat from brick kiln to brick drier and what temperature is required to maintain at the tunnel to dry adobe bricks adequately

0 Answers

How EVA granules manufactured (I wanted to know the manufacturing process). (Virgin Granules) and what are the Raw Materials used.

0 Answers LG, Renewsys,

what are the different types of database servers

0 Answers IBM,

What is a superheterodyne receiver?

2 Answers

For more Engineering AllOther Interview Questions Click Here