Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

Marks: 3 M

Year: Dec 2014

Big-O notation

1. The mathematical tools to represent time complexity of algorithms for asymptotic analysis are called as asymptotic notations.
2. Big-O is a notation used to measure time complexity of program.
3. Basically, Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.
4. This notation defines an upper bound of an algorithm.
5. The function $f(n)=O(g(n))$ if and only if $fn\lt=c.g(n) for all n\gt=no$ where c and no are constants.
6. Here, g(n) is known as upper bound on values of f(n).
7. E.g. $f(n)=3n+3, g(n)=4n$.