Big O Notation in data structure

The Big O notation, where O stands for ‘order of’, is concerned with what happens for very large values of n. For example, if a sorting algorithm performs n² operations to sort just n elements, then that algorithm would be described as an O(n² ) algorithm

When expressing complexity using the Big O notation, constant multipliers are ignored. So, an O(4n) algorithm is equivalent to O(n), which is how it should be written.

If f(n) and g(n) are the functions defined on a positive integer number n, then

f(n) = O(g(n))

That is, f of n is Big–O of g of n if and only if positive constants c and n exist, such that f(n)£cg(n). It means that for large amounts of data, f(n) will grow no more than a constant factor than g(n). Hence, g provides an upper bound. Note that here c is a constant which depends on the following factors:

• the programming language used,
• the quality of the compiler or interpreter
• the CPU speed
• the size of the main memory and the access time to it
• the knowledge of the programmer, and
• the algorithm itself, which may require simple but also time-consuming machine instructions

If f(n) ≤ cg(n), c > 0, ∀ n ≥ n0 , then f(n) = O(g(n)) and g(n) is an asymptotically tight upper bound for f(n)

Categories of Algorithms

According to the Big O notation, we have five different categories of algorithms:

• Constant time algorithm: running time complexity given as O(1)
• Linear time algorithm: running time complexity given as O(n)
• Logarithmic time algorithm: running time complexity given as O(log n)
• Polynomial time algorithm: running time complexity given as O(n^k ) where k > 1
• Exponential time algorithm: running time complexity given as O(2ⁿ )

Limitations of Big O Notation

There are certain limitations with the Big O notation of expressing the complexity of algorithms. These limitations are as follows:

• Many algorithms are simply too hard to analyse mathematically.
• There may not be sufficient information to calculate the behaviour of the algorithm in the average case.
• Big O analysis only tells us how the algorithm grows with the size of the problem, not how efficient it is, as it does not consider the programming effort.
• It ignores important constants. For example, if one algorithm takes O(n2 ) time to execute and the other takes O(100000n2 ) time to execute, then as per Big O, both algorithm have equal time complexity. In real-time systems, this may be a serious consideration