53 views

Given the following code segment, the value in the variable sum is best given by:

sum=0;

for(i=0 ; i< n ;i++)

{

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

{

sum + = i ;

}

}

1. O(nlogn)
2. O(n^3)
3. O(n^2logn)
4. None

| 53 views

Inner loop i.e. $for(j=1;j<n;j*=2)$ always runs $\log{n}$ times. And for each iteration of inner loop, $i$ is added to sum.

Hence, each value of $i$ will be added $\log n$ times. So, sum will be:

$0*\log n+1*\log n+\dots +(n-1)*\log n$

$=(0+1+2+\dots+(n-1))*\log n$

$=(\frac{(n-1)*n}{2})*\log n$                      $(\because \text{left part is sum of integers from 0 to (n-1)})$

$=\frac{(n^2-n)}{2}\log n$

$=\frac{(n^2\log n) – (n\log n)}{2}$

Ignoring constants and lower order terms, we get $O(n^2\log n).$

Hence, option C is the correct answer.
by (855 points)
edited
+1 vote
O(nlogn) because it will it will be like first loop for n time another for logn
by (11 points)
+3
$O(n\log n)$ is the time complexity, but the value of variable $sum$ is asked, and instead of incrementing $sum$ by $1$, it is incremented by $i.$

We have to write expression for sum in terms of n. Since both loops are independent,so for each value of i ,j will execute logn times

and sum = sum + i…...so

for i = 0, j will execute logn times so will be sum =sum + 0,value of sum = logn * 0

for i = 1, j will execute logn times so will be sum =sum + 1,value of sum = logn * 1

for i = 2, j will execute logn times so will be sum =sum + 2 ,value of sum = logn * 2

…………..

for i = n-1, j will execute logn times so will be sum =sum + n ,value of sum = logn * n

Total sum = 0 + logn * 1 + logn * 2 +…….+ logn * (n-1) = (n^2+n)/2 *logn

but here in terms of big O , we have O(n^2 * logn)

Hence, option C is the correct answer.

by (17 points)