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**

**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(N^{2} ).

**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 N^{2} 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 ( N^{2}) time.

(Adapted from “* Cracking The Coding Interview*“)

**The Easy Way of Calculating Big O**

**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(n ^{2})**

**More Examples**

**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 n^{2} times. While the second sum++ expression is executed n * n^{2} times. Thus the running time is approximately n^{2} + n^{3}. As we only consider the dominating term – the Big O Notation of this fragment is expressed by O(n^{3}).

Note that there were two sequential statements therefore we added n^{2} to n^{3}. 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(n ^{5})**.

//Example 4 for(int i = 0; i<2^{10}; i++) for(int j = 0; j < n; j++) sum++;

Note that the outer loop runs 2^{10 }times while the inner loop runs n times.

Hence the running time is:**2 ^{10} * n.** The Big O Notation of this Fragment is expressed by

**O(n)**(ignoring constants).

**One More…**

**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 2^{5} = 32 therefore log_{2 }32 = 5. Thus the running time is actually **log _{2} n**, but we can ignore the base.) Hence the Big O Notation of Example 5 is expressed by

**O(nlogn )**(Multiplication Rule.)

**Further Reading**

**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