 |
| Big-O Notation |
Why ? How ?
To estimate the efficiency of an algorithm, the programmer has to be able to estimate the number of operations if requires to be executed. Usually the number of operations is estimated as a function of a parameter (like the number of data to work on, or the expected precision of a computation, etc.)
For example :
for(i = 0; i < n; i++) { ... }
has a cost proportional to n.
for(i = 1; i < n; i = i*2) { ... }
has a cost proportional to log2 n
for(i = 0; i < n; i++) for(j = 0; j<n*n; j++) { ... }
has a cost proportional to n3.
Definition of O(.)
The classical way to denote an approximation of a complexity is to use the O(.) notation (called “big-O”). If n is a parameter and f(n) the exact number of operations required for that value of the parameter, then we will denote f(n) = O(T (n)) and say that f is a big-O of T if and only if :
∃c, N, ∀n ≥ N, f(n) ≤ c.T (n) it means that f is asymptotically bounded by a function proportional to T .
Note : a same function can be bounded by different expressions, and the = symbol is odd. Using ∈ would have been a better choice.
Some O(.)
Usually the O(.) notation is useful to hide some superfluous details.
For example if f(n) = n2 + 3n than for
n ≥ 3
we have
3n ≤ n2
and thus
f(n) ≤ 2n2
Finally f(n) = O(n2).
Summing O(.)s
f1(n) = O(T (n)) and f2(n) = O(T (n)) ⇒ f1(n) + f2(n) = O(T (n))
Proof :
f1(n) = O(T (n)) ⇒ ∃c1,N1, ∀n ≥ N1, f1(n) ≤ c1 T (n)
f2(n) = O(T (n)) ⇒ ∃c2,N2, ∀n ≥ N2, f2(n) ≤ c2 T (n)
than we have
∀n ≥ max(N1,N2), f1(n) + f2(n) ≤ (c1 + c2)T (n)
The same proof works for products.
Combining O(.)s
f(n) = O(T (n)) and T (n) = O(S(n)) ⇒ f(n) = O(S(n))
Proof :
f(n) = O(T (n)) ⇒ ∃c,N, ∀n ≥ N, f(n) ≤ c T (n)
T (n) = O(S(n)) ⇒ ∃d,M, ∀n ≥ M, T (n) ≤ d S(n)
than we have
∀n ≥ max(N,M), f(n) ≤ c d S(n)