For loop run time

Question

I seem to understand the basic concepts of simpler loops, for example ... the first loop works in O (n), like the inner loop. Since they are both nested, you multiply to get the total running time of O (n ^ 2).

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

Although, when everything begins to change, I am completely lost in how to understand this. Can someone explain to me how to determine the running time for both of the following? Any links to easy to understand links that may help me improve are also welcome. Thanks!

 sum = 0; for( i = 0; i < n; i += 2 ) for( j = 0; j < n; j++ ) ++sum; 

The only thing I can learn from this is that the inner loop works in O (n). i + = 2 really casts me in the outer loop.

 sum = 0; for( i = 1; i < n; i *= 2 ) for( j = 0; j < n; j++ ) ++sum; 

From my attempt ... the outer loop is O (log (n)), the inner is O (n), so total is O (n log (n))?

Answer 1

A good way of thinking about Big-O performance is to pretend that each element of the code is a mathematical function that takes n elements and returns the number of calculations performed on these elements.

For example, a single for loop like for ( i = 0; i < n; i++ ) would be equivalent to the function i() , where i(n) = n , indicating that one calculation is performed for each input n .

If you have two nested loops, then the functional equivalent for

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

will look like these two functions:

 i(n) = n * j(n) j(n) = n 

The work of these two functions gives the final result n*n = n^2 , since j(n) can be replaced by n .

This means that as long as you can solve any single loop for Big-O, you can apply these solutions to a group of nested loops.

For example, consider your second problem:

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

i+=2 means that for a set of input data n items (n0, n1, n2, n3, n4) you touch only every other element of this set. Assuming that you are initialized so that i=0 , this means that you are only touching the set (n0,n2,n4) . This means that you are reducing the size of the data set that you use for processing, and means that functional equivalents work like this:

 i(n) = (n/2) * j(n) j(n) = n 

Solving them, you get (n/2) * n = (n^2)*(1/2) . Since this is a Big-O job, we remove the constants to get the Big-O value (n^2) .

Two key points to remember here:

• Big-O math begins with a set of data elements n . If you are trying to define a Big-O for loop that iterates through this set of n elements, your first step is to see how the incrementor changes the number of data elements that are executed by the for subroutine.

• Maths Big-O is maths. If you can solve for each expression individually, you can use these solutions to create your final answer, as you can solve for a set of equations with common definitions.