Why study algorithms and
performance?
• Algorithms help us to understand scalability.
• Performance often draws the line between what
is feasible and what is impossible.
• Algorithmic mathematics provides a language
for talking about program behavior.
• Performance is the currency of computing.
• The lessons of program performance generalize
to other computing resources.
• Speed is fun!
Asymptotic Complexity
• Running time of an algorithm as a function of
input size n for large n.
• Expressed using only the highest-order term
in the expression for the exact running time.
– Instead of exact running time, say Θ(n2).
• Describes behavior of function in the limit.
• Written using Asymptotic Notation.
Asymptotic Notation
• Θ, O, Ω, o, ω
• Defined for functions over the natural numbers.
– Ex: f(n) = Θ(n2).
– Describes how f(n) grows in comparison to n2.
• Define a set of functions; in practice used to compare
two function sizes.
• The notations describe different rate-of-growth
relations between the defining function and the
defined set of functions.
Comp 122
Θ-notation
For function g(n), we define Θ(g(n)),
big-Theta of n, as the set:
Θ(g(n)) = {f(n) :
∃ positive constants c1, c2, and
n0, such that ∀n ≥ n0,
we have 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)
}
Intuitively: Set of all functions that
have the same rate of growth as g(n).
g(n) is an asymptotically tight bound for f(n).
Comp 122
O-notation
For function g(n), we define O(g(n)),
big-O of n, as the set:
O(g(n)) = {f(n) :
∃ positive constants c and n0,
such that ∀n ≥ n0,
we have 0 ≤ f(n) ≤ cg(n) }
Intuitively: Set of all functions whose rate of
growth is the same as or lower than that of
g(n).
g(n) is an asymptotic upper bound for f(n).
f(n) = Θ(g(n)) ⇒ f(n) = O(g(n)).
Θ(g(n)) ⊂ O(g(n)).
Comp 122
Example
Ω(g(n)) = {f(n) : ∃ positive constants c and n0, such
that ∀n ≥ n0, we have 0 ≤ cg(n) ≤ f(n)}
• √n = Ω(lg n). Choose c and n0.
Comp 122
Relations Between Θ, O, Ω
Comp 122
Relations Between Θ, Ω, O
Theorem : For any two functions g(n) and f(n),
f(n) = Θ(g(n)) iff
f(n) = O(g(n)) and f(n) = Ω(g(n)).
• I.e., Θ(g(n)) = O(g(n)) ∩ Ω(g(n))
• In practice, asymptotically tight bounds are
obtained from asymptotic upper and lower
bounds.
Comp 122
Examples
• Consider the following functions:
f(n) = n
g(n) = n/8
For f(n) = θ(g(n)), find c1, c2 and n0.
C1 = 1, C2=8, n0 =1
• Consider the following functions:
f(n) = n2
g(n) = n
For f(n) = big omega(g(n))
Cn <= n2 for all n>=n0
C=1 and n0 =1
Exercise
• 10n4 + 5n + 7 = O(n4) Find C and n0
• 10n4 + 5n + 7 = Ω(n4) Find C and n0
•
Examples
– n2/2 –n/2 = Θ(n2)
– have 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n)
• ½ n2 - ½ n ≤ ½ n2 ∀n ≥ 0 ⇒ c2= ½
• ½ n2 - ½ n ≥ ½ n2 - ½ n * ½ n ( ∀n ≥ 2 ) = ¼ n2 ⇒ c1= ¼
– n ≠ Θ(n2): c1 n2 ≤ n ≤ c2 n2
⇒ only holds for: n ≤ 1/c
1
12
Examples
– 6n ≠ Θ(n ): c1 n ≤ 6n ≤ c2 n2
3 2 2 3
⇒ only holds for: n ≤ c2 /6
– n ≠ Θ(logn): c1 logn ≤ n ≤ c2 logn
⇒ c2 ≥ n/logn, ∀ n≥ n0 – impossible
13
Example of log n!
Recall that 1! = 1 and n! = (n-1)! n.
Theorem: log n! = Θ(n log n)
Proof:
log n! = log 1 + log 2 + … + log n
<= log n + log n + … + log n = n log n
Hence, log n! = O(n log n).
log n!
On the other hand,
log n! = log 1 + log 2 + … + log n
>= log (⎣(n+1)/2⎦) + … + log n
>= (⎣(n+1)/2⎦) log (⎣(n+1)/2⎦)
>= n/2 log(n/2)
= Ω(n log n)
For the last step, note that
lim infn->∞ (n/2 log(n/2))/(n log n) = ½.
More Examples
• For each of the following pairs of functions, either f(n) is
O(g(n)), f(n) is Ω(g(n)), or f(n) = Θ(g(n)). Determine which
relationship is correct.
– f(n) = log n2; g(n) = log n + 5 f(n) = Θ
– f(n) = n; g(n) = log n2 (g(n))
f(n) = Ω
– f(n) = log log n; g(n) = log n (g(n))
f(n) = O(g(n))
– f(n) = n; g(n) = log2 n f(n) = Ω
– f(n) = n log n + n; g(n) = log n (g(n))
f(n) = Ω
– f(n) = 10; g(n) = log 10 (g(n))
f(n) = Θ
(g(n))
– f(n) = 2n; g(n) = 10n2 f(n) = Ω
n n (g(n))
f(n) = O(g(n))
– f(n) = 2 ; g(n) = 3
16
Properties
• Theorem:
f(n) = Θ(g(n)) ⇔ f = O(g(n)) and f = Ω(g(n))
• Transitivity:
– f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⇒ f(n) = Θ(h(n))
– Same for O and Ω
• Reflexivity:
– f(n) = Θ(f(n))
– Same for O and Ω
• Symmetry:
– f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n))
• Transpose symmetry:
– f(n) = O(g(n)) if and only if g(n) = Ω(f(n))
17
Asymptotic Notations in Equations
• On the right-hand side
– Θ(n2) stands for some anonymous function in Θ(n2)
2n2 + 3n + 1 = 2n2 + Θ(n) means:
There exists a function f(n) ∈ Θ(n) such that
2n2 + 3n + 1 = 2n2 + f(n)
• On the left-hand side
2n2 + Θ(n) = Θ(n2)
No matter how the anonymous function is chosen on
the left-hand side, there is a way to choose the
anonymous function on the right-hand side to make
the equation valid.
18
Common Summations
• Arithmetic series:
• Geometric series:
– Special case: |x| < 1:
• Harmonic series:
• Other important formulas:
19
Mathematical Induction
• A powerful, rigorous technique for proving that
a statement S(n) is true for every natural
number n, no matter how large.
• Proof:
– Basis step: prove that the statement is true for n = 1
– Inductive step: assume that S(n) is true and prove
that S(n+1) is true for all n ≥ 1
• Find case n “within” case n+1
20
Example
• Prove that: 2n + 1 ≤ 2n for all n ≥ 3
• Basis step:
– n = 3: 2 * 3 + 1 ≤ 23 ⇔ 7 ≤ 8 TRUE
• Inductive step:
– Assume inequality is true for n, and prove it for
(n+1):
2n + 1 ≤ 2n must prove: 2(n + 1) + 1 ≤ 2n+1
2(n + 1) + 1 = (2n + 1 ) + 2 ≤ 2n + 2 ≤
≤ 2n + 2n = 2n+1, since 2 ≤ 2n for n ≥ 1
21
