Awesome q2a theme

+3 votes

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 ;

}

}

- O(nlogn)
- O(n^3)
- O(n^2logn)
- None

+3 votes

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.

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.

+1 vote

0 votes

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.

8,446 questions

2,720 answers

13,274 comments

95,468 users