What is the Big O for each of the following code? 1 for ( i = 0; i < n; i ++ ) {
ID: 663648 • Letter: W
Question
What is the Big O for each of the following code?
1 for ( i = 0; i < n; i ++ )
{ j += i; }
2. for ( k = n; k > 0; k-- )
{ j = k * 2;
for ( j = 0; j < 2*n; j++ )
tot = tot + j * k;
}
3. i = n * n;
while ( i > 0 )
{ acc = acc + i * i;
i = i / 2;
}
4. for ( i = 0; i < n; i ++ )
{ j += i; }
i = n * n;
while ( i > 0 )
{ acc = acc + i * i;
i = i / 2;
}
5. for ( i = 0; i < n; i ++ )
{ k = n * n;
while ( k > 0 )
{ acc = acc + k * i;
k = k / 2;
}
}
Explanation / Answer
1) for ( i = 0; i < n; i ++ ){
j += i;
}
Since there is one loop from 0 to n-1
so O(n)
2) for ( k = n; k > 0; k-- ){
j = k * 2; // This line is of no use as j is modified to 0 in next step
for ( j = 0; j < 2*n; j++ )
tot = tot + j * k;
}
first loop is of O(n)
Inside loop is O(2n)
so Total
2*n + 2*n ...... n times
2*n^2
=> O(n ^ 2)
3) i = n * n;
while ( i > 0 ){
acc = acc + i * i;
i = i / 2;
}
is time i become half its previous value.
So log(initial value of i)
so log(n^2)
=> 2*log(n)
4) for ( i = 0; i < n; i ++ ){
j += i;
}
i = n * n;
while ( i > 0 ){
acc = acc + i * i;
i = i / 2;
}
=> 1st loop is O(n)
2nd loop is 2*O(log n)
so total is
O(n) + O(log n)
=> O(n)
5) for ( i = 0; i < n; i ++ ){
k = n * n;
while ( k > 0 ){
acc = acc + k * i;
k = k / 2;
}
}
one loop is inside another
so 2*log(n) + 2*log(n) ... n times
=> 2*n*log(n)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.