Programming Tutorials and Interview Questions

Big-O notation is an asymptotic analysis method for measuring an algorithm's time complexity. Because big-O notation is asymptotic, it gives approximate estimate. Asymptotic notations are used when no exact estimates can be computed. Big O notation is an upper bound of an algorithm's run time complexity. Big-O notation for asymptotic analysis was introduced by Paul Bachmann in 1894 and popularized in subsequent years by Edmund Landau and others.

In big-O analysis, we analyze an algorithm's run time complexity for an input size. For a while, assume that input size is `n`

(for an example, `n`

could be the number of elements in an array or number of nodes in a linked list or the number of bits in a data type or something else depending upon what problem is being solved). After figuring out what `n`

is in terms of the input, we have to determine how many times the `n`

input items are examined in terms of `n`

assuming that every operation or iteration or examination is equivalent and takes constant time.

To understand big-O analysis, we develop a small C function `returnMax`

which takes an array of integers of size `n`

and returns the largest element among array elements.

/* C function to return the largest element from an array. */ #include <stdio.h> #define N 10 /* Returns the largest integer in the array */ int returnMax(int array[], int n) { int curMax, i; /* Make sure array size is not zero. */ if (n <= 0) return -1; /* Initially set the largest number to the first array element. */ curMax = array[0]; /* Compare every element with the largest one till now. */ for (i = 1; i < n; i++) { if (array[i] > curMax) { curMax = array[i]; } } return curMax; } int main (void) { int arr[10] = {1, 9, 2, 8, 3, 7, 4, 6, 10, 5}; int max; max = returnMax(arr, N); printf("%d is the largest element in the array.\n"); return 0; } OUTPUT ====== 10 is the largest element in the array.

In above C function `returnMax`

, "examine" means comparing an array value to another value. In `returnMax`

, each array element was compared once to a maximum value. Thus, the `n`

input items are each examined once, resulting in `n`

examinations. This is considered *O(n)*, usually referred to as linear time: The time required to run the algorithm increases linearly with the number of input items. You may have noticed that in addition to examining each element once, there is a check to ensure that the array is not empty and a step that initializes the `curMax`

variable. It may seem more accurate to call this an *O(n + 2)* function to reflect these extra operations. Big-O analysis, however, yields the asymptotic running time, the limit of the running time as `n`

gets very large. As `n`

approaches infinity, the difference between `n`

and `n + 2`

is insignificant, so the constant term can be ignored. Thus, in big-O analysis we eliminate all but the highest-order term, the term that is largest as `n`

gets very large. In this case, `n`

is the highest-order term. Therefore, the `returnMax`

function is *O(n)*.

The fastest-possible running time for any run-time analysis is *O(1)*, commonly referred to as *constant running time*. An algorithm with constant running time always takes the same amount of time to execute, regardless of the input size.

The general procedure for big-O run-time analysis is as follows:

- Figure out what the input is and what
`n`

represents. - Express the number of operations the algorithm performs in terms of
`n`

. - Eliminate all but the highest-order terms.
- Remove all constant factors.

Big-O analysis should be straightforward if we are able to identify the input size, and the operations correctly that are dependent on the input size.

The BBCâ€™s technology correspondent Rory Cellan-Jones gets a beer poured for him by a robotic barman - but how long does it take?

US politicians have voted to let ISPs gather and sell data about what Americans do online.

Customers who suffer poor service could get automatic payouts under Ofcom's plan.