20 views
int s=0;
for(int b=1;b<=n;b*=2)
{
for(int i=0;i<b;i++)
{
for(int j=0;j<n;j+=2)
{
s=s+j;
}

for(int j=1;j<n;j*=2)
{
s=s+j;
}
}
}

What is the TC of above code? Please illustrate the sigma summation method.

ago | 20 views
0
is it $O\left ( n^{3} \right )?$
0
They've given O(n^2)
0

+1 vote

I think its $O(n^2)$.

The inner most for loops:

for(int j=0;j<n;j+=2)

Takes $O(n)$

for(int j=1;j<n;j*=2)

Takes $O(logn)$

Since they are in sequence : $O(n) + O(logn) = O(n)$

Now evaluate outside in:

 b 1 2 4 8 .... .... .... .... $2^k = n$ i ( 0 to b) 1 time 2 times 4 times 8 times $2^k$ times innermost $O(n)$ $O(n)$ $O(n)$ $O(n)$ $O(n)$ Total n times 2n times 4n times 8n times $2^k * n$ times

Sum up the total number of times:

$= n + 2n + 4n+ 8n+......+2^k *n$

$= n (1 + 2 + 4 + 8 + ...... + 2^k)$

Also $2 ^k = n \implies k = log n$

$= n (1 + 2 + 4 + 8 + ...... log n\:times)$

Apply the GP summation $a*\frac{(r^p - 1)}{r -1}$, here $a = 1, r = 2, p = log n$

$= n*(1 *\frac{2^{logn}-1}{2-1})$

$= n*(1 *\frac{n-1}{1})$

Which is clearly $O(n^2)$

ago by (1.2k points)
selected ago