Order of an Operation (Big O Notation)

The order of an operation refers to the amount of time an operation takes to complete. As a general rule, an algorithm runs with constant time if it works on a single piece of data. 

On the other hand, the order of an operation can vary greatly when dealing with collections.

1. Constant Time – O(1)

O(1) operations always take approximately the same amount of time, regardless of the size of a collection.

1.1 Array

Accessing an element in an array is a constant time operation, since the index is just an offset to the start of the array.

public int GetValueAtLocation(int[] arr, int index) {     // Bounds checking     if (arr == null) throw new ArgumentNullException();     if (index < 0 || index >= arr.Length) throw new ArgumentException();     // This operation runs with constant time     return arr[index]; }

1.2 Hashtable

Retrieving a value from a hashtable using a key can be done in almost linear time, depending in the implementation of the hashtable.

The time of retrieval depends on how well the hash key is implemented for the type being used as a key.

2. Log Time – O (Log(N))

Some operations take the log of the number of items to perform.

2.1 Binary Search

Binary search is used to find an item in a sorted array. With binary search, we half the number of elements we need to search during every iteration.

Find Smallest Integer

1. /// <summary>
2. /// Using binary search, find smallest int in array
3. /// that has been sorted and rotated an unknown number of times.
4. /// <example>
5. /// arr = {93, 105, 124, 7, 23, 45, 87}
6. /// returned index is 3
7. /// </example>
8. /// </summary>
9. static int FindSortedArrayRotation(int[] arr)
10. {
11.     if (arr == null) throw new ArgumentNullException();
12.     if (arr.Length == 0) throw new ArgumentException();
13.  
14.     int left = 0;
15.     int right = arr.Length - 1;
16.     int center = right / 2;
17.  
18.     if (arr[left] <= arr[right]) return 0;
19.  
20.     while (true)
21.     {
22.         if (left + 1 == right)
23.         {
24.             if (arr[left] < arr[right])
25.             {
26.                 return left;
27.             }
28.             else
29.             {
30.                 return right;
31.             }
32.         }
33.         else if (arr[left] > arr[center])
34.         {
35.             left = center;
36.         }
37.         else
38.         {
39.             right = center;
40.         }
41.         center = (right - left) / 2 + left;
42.     }
43. }

3. Linear Time O(N)

The amount of time an O(N) operations takes place is proportional to the number of elements the algorithm is working on.

3.1 Search Unsorted Array

To search an unsorted array, we need to go through all the elements one at a time until we find what we are looking for.

Search for value

1. public int Search(int[] arr, int val)
2. {
3.     for (int i = 0; i < arr.Length; i++)
4.     {
5.         if (arr[i] == val)
6.             return i;
7.     }
8.  
9.     return -1;
10. }

The important point about the above method is that the ‘for’ loop goes through the array once.

3.2 Perform operation on all elements

By nature this is a linear operation.

Modify all elements

1. public void DoSomething(int[] arr)
2. {
3.     // Do setup
4.     for (int i = 0; i < arr.Length; i++)
5.     {
6.         // Do something
7.     }
8.     // Do cleanup
9. }

4. Non-linear Time O(N²)

With O(N²) time, we go through the array once for every element in the array (worse case).

Bubble Sort

1. public void BubbleSort(int[] arr)
2. {
3.     for (int i = 0; i < arr.Length - 1; i++)
4.     {
5.         for (int j = i + 1; j < arr.Length; j++)
6.         {
7.             if (arr[i] > arr[j])
8.             {
9.                 int t = arr[i];
10.                 arr[i] = arr[j];
11.                 arr[j] = t;
12.             }
13.         }
14.     }
15. }

Note: We know that it is O(N²) because we have two embedded for loops. The order of operation is just the number of embedded loops.

5. Non-linear Time O(N^m)

Here is a trick question. What is the Big O of this operation?

embedded loops

1. public void DoSomething(int[] arr)
2. {
3.     // Do setup
4.  
5.     // loop 1
6.     for (int i = 0; i < arr.Length; i++)
7.     {
8.         // loop 2
9.         for (int j = 0; j < arr.Length; j++)
10.         {
11.             DoAction1();
12.         }
13.  
14.         // loop 3
15.         for (int j = 0; j < arr.Length; j++)
16.         {
17.             // loop 4
18.             for (int j = 0; j < arr.Length; j++)
19.             {
20.                 DoAction2();
21.             }
22.         }
23.     }
24.  
25.     // Do cleanup
26. }

Since we have loop 1, that means we are dealing with a linear operation (at least). Loop 2 is embedded in loop 1, so now we have an O(N²) operation (at least).

The operation also has loop 3. Loop 2 and 3 are side by side, so they don’t affect the order of the operation. It is still O(N²) for now.

For loop 1,2 the order of operation is O(N²).

For loop 1,3,4 the order of operation is O(N³).

The higher order for the second one wins and the overall order of the method becomes O(N³).

Keep in mind that the order of operation for DoAction1 and DoAction2 must be taken into account. The order of operation of all embedded operations must be multiplied.

For the above DoAction1 and DoAction2, we had assumed the operation was in constant time. Now let’s assume the order for DoAction1 is O(N³) and order for DoAction2 is O(N¹).

When we do this, loop 1,2 becomes 2 + 3 = 5, or O(N⁵).

Loop 1,2 becomes 3 + 1 = 4, or O(N⁴).

The first one wins now and the order of operation now becomes O(N⁵).

6. References

• http://BigOCheatSheet.com/
• http://en.wikipedia.org/wiki/Exponentiation

Technorati Tags: Big o Operation,Order,Complexity