The Big O – Calculations

This is a follow-up to my previous post ,where i explained a bit about the concept of Big O.

In this post I will continue and expand further showing you how to calculate the Big O.

Tedious Way of Calculating

The common way of calculating Big O is counting the number of steps the algorithm takes to complete a task.

This is a tedious exercise.Imagine if your input is 10,with that small number is easy to count the steps,what if your input is 1 million,then pit becomes impossible.

Example

void printUnOrderedPairs(int[] array)
{
for(int i=0;i < array.Length; i++)
{
for(int j=i+1; j <array.Length;j++)
{
Console.WriteLine(array[i] + "," +array[j]);
}
}
}

 

Counting the iterations

The first time through j runs for N-1 steps. The second time, it’s N-2 steps. Then N-3 steps. And so on.
Therefore, the number of steps total is:
(N-1) + (N-2) + (N-3) + … + 2 + 1

= 1 + 2 + 3 + … + N-1
= sum of 1 through N-1
The sum of 1 through N-1 is -2- (see”Sum o Integers 1 through N on, so the runtime will
be O(N2 ).

What It Means
Alternatively, we can figure out the runtime by thinking about what the code “means:’ It iterates through
each pair of values for ( i, j) where j is bigger than i.There are N2 total pairs. Roughly half of those will have i < j and the remaining half will have i > j. This
code goes through roughly Nx pairs so it does O(N2) work.
Visualizing What It Does
The code iterates through the following ( i, j) pairs when N = 8:
(0, 1) (0, 2) (0, 3) (0, 4) (0, 5) (0, 6) (0, 7)
(1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (1, ‘7)
(2, 3) (2, 4) (2, 5) (2, 6) (2, 7)
(3, 4) (3, 5) (3, 6) (3, 7)
(4, 5) (4, 6) (4, 7)
(5, 6) (5, 7)
(6, 7)
This looks like half of an NxN matrix, which has size (roughly) N/i. Therefore, it takes O ( N2) time.

(Adapted from “Cracking The Coding Interview“)

The Easy Way of Calculating Big O

The easier way of calculating Big O is using a Principle called “The Multiplication rule” which states:

“The total running time of a statement inside a group of nested loops is the running time of the statements multiplied by the product of the sizes of all the for loops. We need only look at the maximum potential number of repetitions of each nested loop.”

Applying the Multiplication Rule to the above example we get:

The inner for loop potentially executes n times (the maximum value of i will be n-1) and the outer for loop executes n times. The statement sum++; therefore executes not many times less than n * n, so the Big O Notation of the above example is expressed by O(n2)

More Examples

//Example 2
for(int i = 0; i < n*n; i++)
sum++;
for(int i = 0; i < n; i++)
for(int j = 0; j < n*n; j++)
sum++;

We consider only the number of times the sum++ expression within the loop is executed. The first sum expression is executed n2 times. While the second sum++ expression is executed n * n2 times. Thus the running time is approximately n2 + n3. As we only consider the dominating term – the Big O Notation of this fragment is expressed by O(n3).

Note that there were two sequential statements therefore we added n2 to n3. This problem illustrates another rule that one may apply when determining the Big O. You can combine sequences of statements by using the Addition rule, which states that the running time of a sequence of statements is just the maximum of the running times of each individual statement.

/Example 3
for(int i =0; i < n; i++)
for(int j = 0; j < n*n; j++)
for(int k = 0; k < j; k++)
sum++;

We note that we have three nested for loops: the innermost, the inner and the outer for loops. The innermost for loop potentially executes n*n times (the maximum value of j will be n*n-1). The inner loop executes n*n times and the outer for loop executes n times. The statement sum++; therefore executes not many times less than n*n * n*n * n, so the Big O Notation of Example 2 is expressed by O(n5).

//Example 4
for(int i = 0; i<210; i++)
for(int j = 0; j < n; j++)
sum++;

Note that the outer loop runs 210 times while the inner loop runs n times.

Hence the running time is:210 * n. The Big O Notation of this Fragment is expressed by O(n) (ignoring constants).

One More…

//Example 5
for(int i = 1; i < n; i++)
for(int i = n; i > 1; i = i/2)
sum++;

The first loop runs n times while the second loops runs log n times. (Why? Suppose n is 32, then sum++; is executed 5 times. Note 25 = 32 therefore log32 = 5. Thus the running time is actually log2 n, but we can ignore the base.) Hence the Big O Notation of Example 5 is expressed by O(nlogn ) (Multiplication Rule.)

 

Further Reading

Malik, DS. 2003. Data structures using C++.

 A practical introduction to data structures and algorithm analysis

Introduction to Algorithms, 3rd Edition (MIT Press) 3rd Edition

Cracking the Coding Interview: 189 Programming Questions and Solutions

 

Leave a Reply