4.2k views

Consider the following C function.

int fun1 (int n) {
int i, j, k, p, q = 0;
for (i = 1; i < n; ++i)
{
p = 0;
for (j = n; j > 1; j = j/2)
++p;
for (k = 1; k < p; k = k * 2)
++q;
}
return q;
}

Which one of the following most closely approximates the return value of the function fun1?

1. $n^3$
2. $n(\log n)^2$
3. $n \log n$
4. $n \log(\log n)$

edited | 4.2k views

$i$ loop is executing $n$ times. $j$ loop is executing $\log\ n$ times for each $i$, and so value of $p$ is $\log n$. $k$ loop is executing $\log\ p$ times, which is $log\ log\ n$ times for each iteration of $i$. In each of these $q$ is incremented. So, over all iterations of $i$, $q$ will be incremented $n\ log\ log\ n$ times. So, D choice.

by Veteran (416k points)
edited by
0
but every time when i is incremented q is not incremented by loglogn.....for 1st iteration of i it is becoming loglog1..then for second loglog2..and so on till n....so finally it should be loglog1+loglog2+loglog3+..........+loglogn..
+3
No. You can see the code- value of i is not used in inner loops.
+1
ok thank ...my mistake...i overlooked the second for loop as j>i....
+1
Since the outer loop is running n times, for each value of outer loop second loop runs (log n) times and for each value of second loop the third loop runs (log(log n)) times, shouldn't the final value be n*(log n)*log(log n)? Obviously i must be doing something wrong since that's not in the options, can you please correct me.
+4

@arjun sir ,

Here ,

• Outer Loop (loop of i) executes N times
• Middle Loop (loop of j) executes log N  time
• Inner Loop ( loop of k) executes log log N time

There is no loop unruling needed for middle and inner loop . So we take the worst case of them which is log n

Hence the time complexity of the code will be O(n log n) .  What is wrong with it ?

+4
@Rakesh, Dq it depends on the question. Here we are asked about the return value of 'q'. Not the time complexity of the code.
+1
@arjun sir , If retun value then why not it is
N * log N * log log N ?

How  you are dealing with dependency in middle and innermost loop is not clear for me
+3
There are only 2 nested loops here. And p always has the same value for the innermost loop.
+1

Still not able to make any conclucsion  :(
"p always has the same value for the innermost loop "  Can u explain this a little bit.
Why the complexity for loop of j is not taken ?

+6
int fun1 (int n) {
int i, j, k, p, q = 0;
for (i = 1; i < n; ++i) {
p = 0; ---> (p becomes 0)
for (j = n; j > 1; j = j/2)
++p;
(j loop finished and value of p is log n)
for (k = 1; k < p; k = k * 2)
++q;
}
return q;
}

Why the complexity for loop of j is not taken ?

Because no one asked for this in question.

0
Thank you sir . For the simple explanation :)
0
when n=10 the q value returned is 18 so the 10(log(log10)) must also give me value somewhere around 18 but its not then how come that is the answer. Can u please explain @Arjun Sir
+1

most closely approximates the return value of the function fun1 . try with all other option they give worst approximation.

0
The complexity would be O(n)* (O( logn ) + O( lglgn ))

so the complexity of the program is O(nlogn)

But the return value of the program is O(nlglgn). Correct me if wrong .

Here for loop of i is executing n times

j is executing log n time

Now, k is incrementing log p times

what that p is?

p is no of time j executes

j executes log n times

So, value of p is also log n

So, from here k executes log log n times

So, return value of fun1 is n log log n

Complexity of program O(n log n)

by Veteran (113k points)
+4
time complexity of this program is O(n log n)  and returning value is O(n log log n)
+1
@Dexter

return value taking all values of i,j,k, as k is depend on p.

But, in time complexity, we are only concern with minimum time.

So, time taken by j loop will not matter here.

So, time complexity will be O(n log n).

explained Arjun Sir in previous command. rt?
int fun1 (int n) {
int i, j, k, p, q = 0;
for (i = 1; i < n; ++i) {
p = 0;
for (j = n; j > 1; j = j/2)
++p;   //this "for loop" is ending here
for (k = 1; k < p; k = k * 2)
++q;
}
return q;
}

p is incrementing $logn$ times hence $p=logn$

and after the loop ends, inner "for loop" is also computing $logp$ i.e. $log(logn)$ times.

so final value of $q=n*O(log(logn))$

But what if program is like this:-

int fun1 (int n) {
int i, j, k, p, q = 0;
for (i = 1; i < n; ++i) {
p = 0;
for (j = n; j > 1; j = j/2) {
p++; //here  loop is not ending here
for (k = 1; k < p; k = k * 2)
++q;
}
}
return q;
}

then for one single value of $i$ value of $q$ will be like this

$q=1*1+2*2+4*3+8*4+16*5+32*6+....n*logn$

$q=\sum_{i=1}^{logn}$$2^{i}*i$

$q=n+O(nlogn)$

after every loop we are resetting the value of $p=0$

So, final value of $q=n^{2}*O(logn)$

by Loyal (7.7k points)
0
Can you please explain more how you get this q=1∗1+2∗2+4∗3+8∗4+16∗5+32∗6+....n∗logn for single loop of i.
by Active (1.4k points)
+1 vote
Ans c)

Here for outer loop we have n time run.

Then we have two inner loop and we have to find the complexity of each loop seperately. So, for the j loop we have logn complexity and for k loop we have loglogn complexity.

Now,

Total complexity is,

n( logn + loglogn).

So we get nlogn as answer
by (175 points)

1
2