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 &#61553;(1).
j = 2 * j;
}
i = &#61675;i/2&#61691;;
}
:

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 do you reset or reseed the IDENTITY column?

1 Answers  


THESE POSTS ARE FOR THE DURATION OF FIVE YEARS. AFTER COMPLETION OF FIVE YEARS, THE PERSONNEL POSTED AGAINST THESE POSTS ARE LIKELY TO BE CONTINUED IN NIC. CAN Any body say that what it will be happened after 5 years? does they through us out from NIC? Is it a temporary job of 5 years is the probation period?

1 Answers   NIC,


can u tell me any JAM topics.........and answers also...plz send me.........e-mail: anitha839@gmail.com

1 Answers  


HOW WE CAN CORRELATE THE MA\ECHANICAL POWER TO ELECTRICAL POWER. SUPPOSE IF I WANT A PUMP OF PUMPIG 200 LPM AT 20 METER HEAD MENAS WHAT IS THE POWER NEEDED FOR PUMP IN ELECTRCAL AND HOW CAN WE GET IT

1 Answers  


Person who dicided to go to weekend trip should not exceed 8 hrs driving in a day. Average speed of forward journey is 40 miles/hour . Due to traffic in sundays ,in return journey average speed is 30mph . How far he can select a picnic spot ?

4 Answers   TCS,


in single linked list , each node contains data and address of next node. if middle of list the node is damaged/crashed then how to find where the link is failed and how to get the all the data which is stored after the crashed node?

1 Answers  


why java take 2 byte for charecter???

1 Answers   MAHINDRA,


I want to prepare for PSU's bt i dont know how many PSU's are open for computer science students and what is the competition level for these. So if anybody knows this please guide me through this.

1 Answers  


what is the limitation of mis(management information system) report?

2 Answers   ABS Construction, TATA,


as we know that java is a platform independent language, but we need jvm for the same operating system why?

1 Answers  


Given a set of numbers like 1,2,5,4,1,2,1,7 find the number of faults using LRU.

1 Answers   NetApp,


if the bit string 0111101111101111110 is bit stuffed,what is the output string?

3 Answers  


Categories
  • Civil Engineering Interview Questions Civil Engineering (5086)
  • Mechanical Engineering Interview Questions Mechanical Engineering (4453)
  • Electrical Engineering Interview Questions Electrical Engineering (16638)
  • Electronics Communications Interview Questions Electronics Communications (3918)
  • Chemical Engineering Interview Questions Chemical Engineering (1095)
  • Aeronautical Engineering Interview Questions Aeronautical Engineering (239)
  • Bio Engineering Interview Questions Bio Engineering (96)
  • Metallurgy Interview Questions Metallurgy (361)
  • Industrial Engineering Interview Questions Industrial Engineering (259)
  • Instrumentation Interview Questions Instrumentation (3014)
  • Automobile Engineering Interview Questions Automobile Engineering (332)
  • Mechatronics Engineering Interview Questions Mechatronics Engineering (97)
  • Marine Engineering Interview Questions Marine Engineering (124)
  • Power Plant Engineering Interview Questions Power Plant Engineering (172)
  • Textile Engineering Interview Questions Textile Engineering (575)
  • Production Engineering Interview Questions Production Engineering (25)
  • Satellite Systems Engineering Interview Questions Satellite Systems Engineering (106)
  • Engineering AllOther Interview Questions Engineering AllOther (1379)