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;
}
:
Answers were Sorted based on User's Feedback
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 |
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 |
How do you reset or reseed the IDENTITY column?
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?
can u tell me any JAM topics.........and answers also...plz send me.........e-mail: anitha839@gmail.com
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
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 ?
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?
why java take 2 byte for charecter???
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.
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?
Given a set of numbers like 1,2,5,4,1,2,1,7 find the number of faults using LRU.
if the bit string 0111101111101111110 is bit stuffed,what is the output string?
Civil Engineering (5086)
Mechanical Engineering (4453)
Electrical Engineering (16638)
Electronics Communications (3918)
Chemical Engineering (1095)
Aeronautical Engineering (239)
Bio Engineering (96)
Metallurgy (361)
Industrial Engineering (259)
Instrumentation (3014)
Automobile Engineering (332)
Mechatronics Engineering (97)
Marine Engineering (124)
Power Plant Engineering (172)
Textile Engineering (575)
Production Engineering (25)
Satellite Systems Engineering (106)
Engineering AllOther (1379)