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 n2 operations to sort just n elements, then that algorithm would be described as an O(n2 ) 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(nk ) where k > 1
  • Exponential time algorithm: running time complexity given as O(2n )

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

Leave a Comment