Return value is O(*N ^{2 }logN*)

Time complexity of Program is

*right !!?*

**N logN**
The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+21 votes

Consider the following function:

int unknown(int n){ int i, j, k=0; for (i=n/2; i<=n; i++) for (j=2; j<=n; j=j*2) k = k + n/2; return (k); }

The return value of the function is

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

+43 votes

Best answer

The outer loop is running for $n/2$ times and inner loop is running for $\log_2 n$ times (each iteration doubles $j$ and $j$ stops at $n$ means $\log_2 n$ times $j$ loop will iterate).

Now in each iteration $k$ is incremented by $n/2$. So, overall $k$ will be added $n/2 * log n * n/2$ with an initial value of $0$. So, final value of $k$ will be $\Theta(n^2 log n)$

Now in each iteration $k$ is incremented by $n/2$. So, overall $k$ will be added $n/2 * log n * n/2$ with an initial value of $0$. So, final value of $k$ will be $\Theta(n^2 log n)$

+7 votes

Here we have to tell the value of k returned not the time complexity.

for (i = n/2; i <= n; i++) for (j = 2; j <= n; j = j * 2) k = k + n/2; return k;

The outer loop runs n/2 times The inner loop runs logn times.(2^k = n => k = logn). Now looking at the value of k in inner loop, n is added to k, logn times as the inner loop is running logn times. Therefore the value of k after running the inner loop one time is n*logn. Therefore total time complexity is inner multiplied with outer loop complexity which (n for outer and nlogn for inner) n$^{2}$logn.

+5 votes

here point to be noticed is complexity of returned value is asked but not the complexity of just execution code.so we just count how many times value of k is computed before completion of outer as well as inner loop.

outer loop executes n times

inner loop executes log n base 2 times and each time value of k is incremented by n/2

n/2 + n/2 +n/2..... till second loop executes.

this says after completion of inner loop value of k will be (logn)*n/2

And due to outer loop this calculation occurs for n times

So combining all we get total value as

n*n/2*log(n)

$n^{2}logn$

outer loop executes n times

inner loop executes log n base 2 times and each time value of k is incremented by n/2

n/2 + n/2 +n/2..... till second loop executes.

this says after completion of inner loop value of k will be (logn)*n/2

And due to outer loop this calculation occurs for n times

So combining all we get total value as

n*n/2*log(n)

$n^{2}logn$

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 21
- Job Queries 61
- Projects 13

39,658 questions

46,733 answers

140,424 comments

58,146 users