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.

Developers launch a new app to help pregnant women get a seat on public transport while commuting.

The firm says neither software nor hardware, other than the batteries, were at fault in Note 7.

China is cracking down on the hi-tech ways citizens avoid official scrutiny of what they do online.