Summary
of Big-Oh
·
The number of operations for an algorithm that processes
input of size N can be represented as a function of N: f(N).
·
The complexity of the algorithm depends on the type of f(N).
·
In order to compare algorithms and to choose the best one among
several algorithms we need to be able to compare
functions.
Any
two growing functions f(N) and g(N) can be in one of the three
possible relations:
1.
f(n) =
Θ( g(n) )
f(n) and g(n) have the same rate of growing,
lim( f(n)/g(n) ) = c, 0 < c < ∞,
n → ∞
2.
f(n) = o( g(n)
)
f(n) grows slower than g(n) , lim(f(n)/g(n)) = 0, n
→
∞
3.
f(n) = ω
(g(n))
f(n) grows faster than g(n) , lim( f(n)/g(n) ) = ∞,
n → ∞
The first two relations are combined in
the Big-Oh notation:
f(N)
= O(g(N)) : f(N) grows
with the same rate or slower than g(N)
Rules to
manipulate Big-Oh expressions:
Let
T1(N) and T2(N) be run times, T1(N) = O( f(N) ), T2(N) = O( g(N) )
A.
T1(N) + T1(N) = max( O( f(N) ), O( g(N) ) )
T1(N) * T2(N) = O( f(N) * g(N))
B. If T(N) is a polynomial of degree k, then T(N) = Θ(Nk)
= O(Nk ).
C. logkN = O(N) for any constant k.
Counting the
number of operations
A. for loops
The
running time of a for loop is at most the running time of the
statements inside the loop times the
number of iterations.
sum
= 0;
for(
i = 0; i < n; i++)
sum
= sum + i; // The running time is O(n)
B. Nested
loops
The
total running time is the running time of the inside statements times the
product of the sizes of all the loops
sum = 0;
for( i = 0; i < n; i++)
for( j = 0; j < n; j++)
sum++; //The running time
is O(n2)
Note: Loops that
run in Logarithmic time
for( i = n; i >1; i = i/2 )
{……
}
for( i = 1; i <n; i = i*2 )
{……. }
Running
time: O( [running time of the body] * Log(N))
C. Consecutive
program fragments
The
total running time is the maximum of the running time of the individual
fragments
sum = 0;
for( i = 0; i < n; i++)
sum = sum + i;
sum = 0;
for( i = 0; i < n; i++)
for( j =
0; j < 2n; j++)
sum++;
The
first loop runs in O(n) time, the
second - O(n2) time, the
maximum is O(n2)
D: If
statement
if C S1; else S2;
The
running time is the maximum of the running times of S1 and S2.
Things to watch for:
1.
Is there a
function call whose running time
depends on N?
If yes - its running time has to be taken into
account
2.
The number
of iterations depends on how the loop variable changes -
in a linear way or by a factor of 2 (3, 4, etc),
or modified inside the loop.