Basics of Complexity Analysis:
The RAM Model and the
Growth of Functions
Antonio Carzaniga
Faculty of Informatics
University of Lugano
Semptember 24, 2008
© 2006–2007 Antonio Carzaniga 1
Outline
Informal analysis of two Fibonacci algorithms
The random-access machine model
Measure of complexity
Characterizing functions with their asymptotic behavior
Big-O, omega, and theta notations
© 2006–2007 Antonio Carzaniga 2
Slow vs. Fast Fibonacci
60
Ruby
Python
50 Scheme
C
Time (seconds)
40 C-wiz
Java
C-gcc
30 PythonSmart
20
10
0
0 20 40 60 80 100
n
© 2006–2007 Antonio Carzaniga 3
Slow vs. Fast Fibonacci
We informally characterized our two Fibonacci algorithms
◮ Fibonacci is exponential in n
◮ SmartFibonacci is (almost) linear in n
How do we characterize the complexity of algorithms?
◮ in general
◮ in a way that is specific of the algorithms
◮ but independent of any implementation detail
© 2006–2007 Antonio Carzaniga 4
Slow vs. Fast Fibonacci
Fibonacci
Time SmartFibonacci
© 2006–2007 Antonio Carzaniga 5
A Model of the Computer
An informal model of the random-access machine (RAM)
Basic types in the RAM model
◮ integer and floating-point numbers
◮ limited size of each “word” of data (e.g., 64 bits)
Basic steps in the RAM model
◮ operations involving basic types
◮ load/store: assignment, use of a variable
◮ arithmetic operations: addition, multiplication, division, etc.
◮ branch operations: conditional branch, jump
◮ subroutine call
A basic step in the RAM model takes a constant time
© 2006–2007 Antonio Carzaniga 6
Analysis in the RAM Model
SmartFibonacci(n) cost times (n > 1)
1 if n = 0 c1 1
2 then return 0 c2 0
3 elseif n = 1 c3 1
4 then return 1 c4 0
5 else pprev ← 0 c5 1
6 prev ← 1 c6 1
7 for i ← 2 to n c7 n−1
8 do f ← prev + pprev c8 n−1
9 pprev ← prev c9 n−1
10 prev ← f c10 n−1
11 return f c11 1
T (n) = c1 + c3 + c5 + c6 + c11 + (n − 1)(c7 + c8 + c9 + c10 )
T (n) = nC1 + C2 ⇒ T (n) is a linear function of n
© 2006–2007 Antonio Carzaniga 7
Input Size
In general we measure the complexity of an algorithm as a
function of the size of the input
◮ size measured in bits
◮ did we do that for SmartFibonacci?
Example: given a sequence A = ha1 , a2 , . . . , an i, and a value x,
output true if A contains x
Find(A, x)
1 for i ← 1 to length(A)
2 do if A[i] = x
3 then return true
4 return false
T (n) = Cn
© 2006–2007 Antonio Carzaniga 8
Worst-Case Complexity
In general we measure the complexity of an algorithm in the
worst case
Example: given a sequence A = ha1 , a2 , . . . , an i, output true if
A contains two equal values ai = aj (with i 6= j)
FindEquals(A)
1 for i ← 1 to length(A) − 1
2 do for j ← i + 1 to length(A)
3 do if A[i] = A[j]
4 then return true
5 return false
n(n − 1)
T (n) = C
2
© 2006–2007 Antonio Carzaniga 9
Constant Factors
Does a load/store operation cost more than, say, an arithmetic
operation?
x ← 0 vs. y + z
We do not care about the specific costs of each basic step
◮ these costs are likely to vary significantly with languages,
implementations, and processors
◮ so, we assume c1 = c2 = c3 = · · · = ci
◮ we also ignore the specific value ci , and in fact we ignore every
constant cost factor
© 2006–2007 Antonio Carzaniga 10
Order of Growth
We care only about the order of growth or rate of growth of
T (n)
◮ so we ignore lower-order terms
E.g., in
T (n) = an2 + bn + c
we only consider the n2 term and say that T (n) is a quadratic
function in n
We write
T (n) = Θ(n2 )
and say that “T (n) is theta of n-squared”
© 2006–2007 Antonio Carzaniga 11
Θ-Notation
Given a function g(n), we define the family of functions
Θ(g(n))
c2 g(n)
f (n)
c1 g(n)
n0
Θ(g(n)) = {f (n) : ∃c1 > 0, ∃c2 > 0, ∃n0 > 0
: 0 ≤ c1 g(n) ≤ f (n) ≤ c2 g(n) for all n ≥ n0 }
© 2006–2007 Antonio Carzaniga 12
Examples
T (n) = n2 + 10n + 100 ⇒ T (n) = Θ(n2 )
T (n) = n + 10 log n ⇒ T (n) = Θ(n)
√ √
T (n) = n log n + n n ⇒ T (n) = Θ(n n)
n n
T (n) = 2 6 + n7 ⇒ T (n) = Θ(2 6 )
10+n 1
T (n) = n2
⇒ T (n) = Θ( n )
T (n) = complexity of SmartFibonacci ⇒ T (n) = Θ(n)
We characterize the behavior of T (n) in the limit
The Θ-notation is an asymptotic notation
© 2006–2007 Antonio Carzaniga 13
O-Notation
Given a function g(n), we define the family of functions
O(g(n))
cg(n)
f (n)
n0
O(g(n)) = {f (n) : ∃c > 0, ∃n0 > 0
: 0 ≤ f (n) ≤ cg(n) for all n ≥ n0 }
© 2006–2007 Antonio Carzaniga 14
Examples
T (n) = n2 + 10n + 100 ⇒ T (n) = O(n2 ) ⇒ T (n) = O(n3 )
T (n) = n + 10 log n ⇒ T (n) = O(2n )
√
T (n) = n log n + n n ⇒ T (n) = O(n2 )
n
T (n) = 2 6 + n7 ⇒ T (n) = O((1.5)n )
10+n
T (n) = n2
⇒ T (n) = O(1)
f (n) = Θ(g(n)) ⇒ T (n) = O(g(n))
f (n) = Θ(g(n)) ∧ g(n) = O(h(n)) ⇒ f (n) = O(h(n))
f (n) = O(g(n)) ∧ g(n) = Θ(h(n)) ⇒ f (n) = O(h(n))
© 2006–2007 Antonio Carzaniga 15
Examples
n2 − 10n + 100 = O(n log n)? NO
f (n) = O(2n ) ⇒ f (n) = O(n2 )? NO
f (n) = Θ(2n ) ⇒ f (n) = O(n2 2n )? YES
f (n) = Θ(n2 2n ) ⇒ f (n) = O(2n+2 log2 n )? YES
f (n) = O(2n ) ⇒ f (n) = Θ(n2 )? NO
√
n = O(log2 n)? NO
n
n2 + (1.5)n = O(2 2 )? NO
© 2006–2007 Antonio Carzaniga 16
Example
So, what is the complexity of FindEquals?
FindEquals(A)
1 for i ← 1 to length(A) − 1
2 do for j ← i + 1 to length(A)
3 do if A[i] = A[j]
4 then return true
5 return false
T (n) = Θ(n2 )
◮ n = length(A)
◮ we measure the worst-case complexity
© 2006–2007 Antonio Carzaniga 17
Ω-Notation
Given a function g(n), we define the family of functions
Ω(g(n))
f (n)
cg(n)
n0
Ω(g(n)) = {f (n) : ∃c > 0, ∃n0 > 0
: 0 ≤ cg(n) ≤ f (n) for all n ≥ n0 }
© 2006–2007 Antonio Carzaniga 18
Θ, O, and Ω as Relations
Theorem: for any two functions f (n) and g(n),
f (n) = Ω(g(n)) ∧ f (n) = O(g(n)) ⇔ f (n) = Θ(g(n))
The Θ-notation, Ω-notation, and O-notation can be viewed as
the “asymptotic” =, ≥, and ≤ relations for functions,
respectively
The above theorem can be interpreted as saying
f ≥g∧f ≤g⇔f =g
When f (n) = O(g(n)) we say that g(n) is an upper bound for
f (n), and that g(n) dominates f (n)
When f (n) = Ω(g(n)) we say that g(n) is a lower bound for
f (n)
© 2006–2007 Antonio Carzaniga 19
Θ, O, and Ω as Anonymous Functions
We can use the Θ-, O-, and Ω-notation to represent anonymous
(unknown or unsecified) functions
E.g.,
f (n) = 10n2 + O(n)
means that f (n) is equal to 10n2 plus a function we don’t
know or we don’t care to know that is asymptotically at most
linear in n.
Examples
n2 + 4n − 1 = n2 + Θ(n)? YES
n2 + Ω(n) − 1 = O(n2 )? NO
n2 + O(n) − 1 = O(n2 )? YES
√ √
n log n + Θ( n) = O(n n)? YES
© 2006–2007 Antonio Carzaniga 20
o-Notation
The upper bound defined by the O-notation may or may not be
asymptotically tight
E.g.,
n log n = O(n2 ) is not asymptotically tight
n2 − n + 10 = O(n2 ) is asymptotically tight
We use the o-notation to denote upper bounds that are not
asymtotically tight. So, given a function g(n), we define the
family of functions o(g(n))
o(g(n)) = {f (n) : ∃c > 0, ∃n0 > 0
: 0 ≤ f (n) < cg(n) for all n ≥ n0 }
© 2006–2007 Antonio Carzaniga 21
ω-Notation
The lower bound defined by the Ω-notation may or may not be
asymptotically tight
E.g.,
2n = Ω(n log n) is not asymptotically tight
n + 4n log n = Ω(n log n) is asymptotically tight
We use the ω-notation to denote lower bounds that are not
asymtotically tight. So, given a function g(n), we define the
family of functions ω(g(n))
ω(g(n)) = {f (n) : ∃c > 0, ∃n0 > 0
: 0 ≤ cg(n) < f (n) for all n ≥ n0 }
© 2006–2007 Antonio Carzaniga 22
