Interested to Buy Any Domain ? << Click Here >> for more details...
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;
}
:
- 2 Answers
- 15858 Views
- I also Faced
- E-Mail Answers
Answer Posted / 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 |
Post New Answer View All Answers
how is the config take place and from reciever side how will process the data into internal table
No. of rounds: 1. GD 2. Written test 3. Technical round 4. HR Group Discussion: In GD I got topic “Effect of Movies on Youth, is it good or bad?”. Everyone got chance to speak. They examined the fluency and point of view on topic. I was selected in this round. Written Test: In written, there were 30 to 40 question including 5 subjective, they are, 1 What is RTTI(Run Time Type Information)? 2 What is containership? 3 What is the difference between compiler level of C++, C# and one other language? 4 Why C++ reserve 2 bytes for structure? 5 One question was related to dot net….. Remaining question are objective and they are belongs to C, Data Structure, 4-5 question from Java and also some questions from Software Development, includes, Some programs given with there output, questions related to sorting algorithm and there complexities, from java, multithreading and a program for Concatenation of two strings using inbuilt methods, from Software development they ask about software lifecycle(including all phases), specification and testing. It was all technical and I cleared the written too. Technical round: In this round, they asked about my resume. Remember the things that you write only those things in resume, in which you are very well, else it will create problems for you. They asked first about myself, and then about my programming skills. They give me a problem to solve in C. They ask me about SQL commands (because I mentioned in resume) like difference between delete and truncate, left join with syntax, then some questions from OS and computer network. I also found out that they were taking my stress testing. They fired questions very rapidly. Don’t give up they will make you feel free environment if you will get nervous (at that time I was). HR round: In this round as usual they asked about personal question to starting with about yourself. They asked some IQ questions like which object with four points are at equidistance, draw three co-centric circle without pull-up your hand, they also asked question, if a bear is jump from 1 meter in …sec. what is the color of that bear. Answer is related to measuring gravity according to south and north pole, and I was confused at that time. They also asked the meaning of my name, I gave that answer.
What do you mean by client /server for a post scarcity world
please kindly send me the details about courses that are offered in nda
hi... i just want to know that how could join the AAI with an B.E back ground??? please help me out.
Write steps of retrieving data using ado.net?
How Main()is called by opreting system?
what size shaft is required to transmit 100 hp @1000 RPM ,if max shear stress is 10,000 PSI,angle of twist must be less than 1' /ft/shaft is made of steel.
when will the group1&group2 exams will be held
how to create user name stape by stape in cisco router {with command}
Please derive the formula for the area of a circle.
How we can find out face expression ,what approach should be followed (like skin detection) ?
How we can read an Image in VC++?How we can find out the intensities of the pixels of an image and dimension of the image?
which type of casting enforces type safety
Hi All... PLease send me if anyone have "Information Security Officer" Aptitude papers. Please Mail me at mannusanghi@gmail.com
