# GATE2015-1-31

8.8k 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
0
What the hell, J and K loops are not nested. I got so confused, as in GO book this question got split between pages and me like an idiot applying stirling approximation.

Anyways if they were nested then the answer would've been:

$O(n\hspace{1mm}log\hspace{1mm}n\hspace{1mm}loglog\hspace{1mm}n)$

$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.

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.
5

@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 ?

10
@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 ?

8
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)

5
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?
0
time complexity = n(logn + loglogn) = nlogn ???
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)$

1
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.
int fun1 (int n) {
int i, j, k, p, q = 0;
for (i = 1; i < n; ++i)    // O(n)
{
p = 0;
for (j = n; j > 1; j = j/2)     // O(logn)
++p;
for (k = 1; k < p; k = k * 2)     // O(logp) = O(loglogn)
++q;
}
return q;
}

The return value, ie, q gets the value approximately equal to $loglogn$ for each iteration of the outer-loop.

Hence, overall, q will get the value $nloglogn$

Option D

Note that the second and third for-loops aren't nested with respect to each other.

They coexist as inner loops with the first loop being the outer loop.

So, time complexity would be $O(n*(logn+loglogn))=O(nlogn)$ and not $O(n*logn*loglogn)$

edited
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
1
They didn't ask for time complexity.
1 flag:
✌ Low quality (Hira Thakur)

Hope this hepls :)

1 vote

outermost loop i runs for 'n' times

second loop will run for logn times. and for each i, logn times = nlogn.

as second loop ran for logn times 'p' value is incremented upto logn.

hence innermost loop wil run for loglogn times. (because each time k = k*2 ... hence loop will run upto loglogn times)

Hence complexity will be O(nloglogn)

## Related questions

1
5.5k views
Let a$_{n}$ represent the number of bit strings of length n containing two consecutive $1$s. What is the recurrence relation for $a_{n}$? $a_{n - 2} + a_{n - 1} + 2^{n - 2}$ $a_{n - 2} + 2a_{n - 1} + 2^{n - 2}$ $2a_{n - 2} + a_{n - 1} + 2^{n - 2}$ $2a_{n - 2} + 2a_{n - 1} + 2^{n - 2}$
2
8.9k views
Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$. A breadth first search (BFS) is performed starting at $s$. Let $T$ ... of $G$ that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$? $-1$ $0$ $1$ $2$
3
9.4k views
The graph shown below has $8$ edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight $36$ and contains the edges: $\{(A, C), (B, C), (B, E), (E, F), (D, F)\}$. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all $8$ edges of this graph is_______________.
An algorithm performs $(\log N)^{\frac{1}{2}}$ find operations , $N$ insert operations, $(\log N)^{\frac{1}{2}}$ delete operations, and $(\log N)^{\frac{1}{2}}$ decrease-key operations on a set of data items with keys drawn from ... to use, if the goal is to achieve the best total asymptotic complexity considering all the operations? Unsorted array Min - heap Sorted array Sorted doubly linked list