[Algorithm] Big-O Notation | 빅 오 표기법

Big O notation is a mathematical way of describing how a function (running time of an algorithm) generally behaves in relation to the input size.

 

Given a function that describes the running time of an algorithm, the Big O notation for that function can be determined using the following rules:

1. If f(N) is a sum of several terms, the highest order term (the one with the fastest growth rate) is kept and others are discarded.
2. If f(N) has a term that is a product of several factors, all constants (those that are not in terms of N) are omitted.

 

For example, if the given algorithm steps, f(N) = 7N^2 + 13N + 5, then

O(f(N)) = O(7N^2 + 13N + 5) = O(7N^2) = O(N^2)

 

There are some rules for determining Big O notation for composite functions:

 

Some examples of Big O notation are:

Big O	O(N^2 + 9999)	O(6N^3 + 2N + 3)	10*O(N^4)	2N^3+O(N^2)	O(734N)
Simplified Big O	O(N^2)	O(N^3)	O(N^4)	O(N^3)	O(N)