Describe big-O notation. Write down its characteristics. How
it is used to calculate complexity of an algorithm?
Answers
Answer:
In our previous articles on Analysis of Algorithms, we had discussed asymptotic notations, their worst and best case performance etc. in brief. In this article, we discuss the analysis of the algorithm using Big – O asymptotic notation in complete detail.
Big-O Analysis of Algorithms
We can express algorithmic complexity using the big-O notation. For a problem of size N:
A constant-time function/method is “order 1” : O(1)
A linear-time function/method is “order N” : O(N)
A quadratic-time function/method is “order N squared” : O(N 2 )
Definition: Let g and f be functions from the set of natural numbers to itself. The function f is said to be O(g) (read big-oh of g), if there is a constant c and a natural n 0 such that f (n) ≤ cg(n) for all n > n0 .
Note: O(g) is a set!