Awesome q2a theme
+3 votes
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

 

in Algorithms by (17 points) | 53 views

3 Answers

+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.
by (855 points)
edited by
+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.$
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.

by (17 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,446 questions
2,720 answers
13,274 comments
95,468 users