Big-O, Omega and Theta Notations

Learn the ways to express the limits of a function representing the algorithm complexity.

We'll cover the following

Big-OO notation

Definition: “f(n)f(n) is big-OO of g(n)g(n)” or f(n)f(n) = O(g(n))O(g(n)), if there are two positive constants cc and n0n0 such that f(n)cg(n)f(n) ≤ c g(n) for all nn0n ≥ n0,

In other words, cg(n)c g(n) is an upper bound for f(n)f(n) for all nn0n ≥ n0. The function f(n)f(n) growth is slower than cg(n)c g(n). For a sufficiently large value of input nn, the (c.g(n))(c.g(n)) will always be greater than f(n)f(n).

Example: n2n^{2} + n=On = O(n2n^{2})

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.