Question

1. Show that the running time for the following segment of code is O(N³) without using the rule for loop. Make sure to count each statement that takes one unit of time.

sum = 0;

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

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

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

sum++;

Answer 1

sum = 0;
This line runs for 1 time

for( i = 0; i < n; i++ )
This line runs for n time

for( j = 0; j < n; j++ )
This line runs for n*(n+1) time

for( k = 0; k < n; k++ )
This line runs for n*n*(n+1) time

sum++;
This line runs for n*n*n time

So, time complexity
= 1 + n + n*(n+1) + n*n*(n+1) + n*n*n
= 1 + n + n*n + n + n*n*n + n*n + n*n*n
= 1 + 2*n + 2*n*n + 2*n*n*n
= O(Dominant term in the equation by removing constant multipliers)
= O(n*n*n)
= O(n^3)