Data Structures and Algorithms - Old Questions
5. Describe the Big 'O' notation.
5 marks
|
Asked in 2074
Big-O notation signifies the relationship between the input to the algorithm and the steps required to execute the algorithm.
A function f(n) is said to be “big-Oh of g(n)” and we write, f(n)=O(g(n)) or simply f=O(g), if there are two positive constants c and n0 such that f(n)<=c*g(n) for all n>=n0.
E.g. The big oh notation of f(n)=n+4 is O(n) since n+4<=2n for all n>=4.
The big oh notation of f(n)=n2+3n+4 is O(n2) since n2+3n+4<=2n2 for all n>=4.
Big O notation specifically describes worst case scenario. It represents the upper bound running time complexity of an algorithm.