The Gateway to Computer Science Excellence

+37 votes

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?

- $n^3$
- $n(\log n)^2$
- $n \log n$
- $n \log(\log n)$

+64 votes

Best answer

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

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

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

+6

@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

N * log N * log log N ?

How you are dealing with dependency in middle and innermost loop is not clear for me

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

+7

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 jis not taken ?

Because no one asked for this in question.

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

+31 votes

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

+8 votes

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

+3 votes

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

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 vote

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

0 votes

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,313 answers

198,349 comments

105,051 users