CSE 326
Asymptotic Analysis
David Kaplan
Dept of Computer Science & Engineering
Autumn 2001
Housekeeping
Homework 1 status
Join cse326@cs
Poll:
Slide format(s)?
Office hours today?
Asymptotic Analysis CSE 326 Autumn 2001 2
Analyzing Algorithms
Analyze algorithms to gauge:
Time complexity (running time)
Space complexity (memory use)
Input size is indicated by a number n
sometimes have multiple inputs, e.g. m and n
Running time is a function of n
n, n 2, n log n, 18 + 3n(log n2) + 5n3
Asymptotic Analysis CSE 326 Autumn 2001 3
RAM Model
RAM (random access machine)
Ideal single-processor machine (serialized
operations)
“Standard” instruction set (load, add, store, etc.)
All operations take 1 time unit (including, for our
purposes, each C++ statement)
Asymptotic Analysis CSE 326 Autumn 2001 4
Order Notation (aka Big-O)
T(n) = O( f(n) )
Big-O Exist positive constants c, n0 such that Upper bound
T(n) cf(n) for all n n0
T(n) = ( f(n) )
Omega Exist positive constants c, n0 such that Lower bound
T(n) cf(n) for all n n0
T(n) = θ( f(n) )
Theta Tight bound
T(n) = O(f(n)) AND T(n) = (f(n))
T (n ) = o ( f (n ) ) Strict upper
little-o T(n) = O(f(n)) AND T(n) != θ(f(n)) bound
Asymptotic Analysis CSE 326 Autumn 2001 5
Simplifying with Big-O
By definition, Big-O allows us to:
Eliminate low order terms
4n + 5 4n
0.5 n log n - 2n + 7 0.5 n log n
Eliminate constant coefficients
4n n
0.5 n log n n log n
log n2 = 2 log n log n
log3 n = (log3 2) log n log n
But when might constants or low-order terms matter?
Asymptotic Analysis CSE 326 Autumn 2001 6
Big-O Examples
n2 + 100 n = O(n2)
follows from … ( n2 + 100 n ) 2 n2 for n 10
n2 + 100 n = (n2)
follows from …( n2 + 100 n ) 1 n2 for n 0
n2 + 100 n = (n2)
by definition
n log n = O(n2)
n log n = (n log n)
n log n = (n)
Asymptotic Analysis CSE 326 Autumn 2001 7
Big-O Usage
Order notation is not symmetric:
we can say 2n2 + 4n = O(n2)
… but never O(n2) = 2n2 + 4n
Right-hand side is a crudification of the left
Order expressions on left can produce unusual-
looking, but true, statements:
O(n2) = O(n3)
(n3) = (n2)
Asymptotic Analysis CSE 326 Autumn 2001 8
Big-O Comparisons
Function A Function #2
n3 + 2n2 100n2 + 1000
n0.1 log n
vs.
n + 100n0.1 2n + 10 log n
5n5 n!
n-152n/100 1000n15
82log n 3n7 + 7n
Asymptotic Analysis CSE 326 Autumn 2001 9
Race 1
n3 + 2n2 vs. 100n2 + 1000
Asymptotic Analysis CSE 326 Autumn 2001 10
Race 2
n0.1 vs. log n
In this one, crossover point is very late! So, which algorithm is really better???
Asymptotic Analysis CSE 326 Autumn 2001 11
Race C
n + 100n0.1 vs. 2n + 10 log n
Is the “better” algorithm asymptotically better???
Asymptotic Analysis CSE 326 Autumn 2001 12
Race 4
5n5 vs. n!
Asymptotic Analysis CSE 326 Autumn 2001 13
Race 5
n-152n/100 vs. 1000n15
Asymptotic Analysis CSE 326 Autumn 2001 14
Race VI
82log(n) vs. 3n7 + 7n
Asymptotic Analysis CSE 326 Autumn 2001 15
Big-O Winners (i.e. losers)
Function A Function #2 Winner
n3 + 2n2 100n2 + 1000 O(n2)
n0.1 log n O(log n)
vs.
n + 100n0.1 2n + 10 log n O(n) TIE
5n5 n! O(n5)
n-152n/100 1000n15 O(n15)
82log n 3n7 + 7n O(n6) why???
Asymptotic Analysis CSE 326 Autumn 2001 16
Big-O Common Names
constant: O(1)
logarithmic: O(log n)
linear: O(n)
log-linear: O(n log n)
superlinear: O(n1+c) (c is a constant > 0)
quadratic: O(n2)
polynomial: O(nk) (k is a constant)
exponential: O(cn) (c is a constant > 1)
Asymptotic Analysis CSE 326 Autumn 2001 17
Kinds of Analysis
Running time may depend on actual input, not
just length of input
Distinguish
Worst case
Your worst enemy is choosing input
Average case
Assume probability distribution of inputs
Amortized
Average time over many runs
Best case (not too useful)
Asymptotic Analysis CSE 326 Autumn 2001 18
Analyzing Code
C++ operations constant time
Consecutive stmts sum of times
Conditionals larger branch plus test
Loops sum of iterations
Function calls cost of function body
Recursive functions solve recursive equation
Asymptotic Analysis CSE 326 Autumn 2001 19
Nested Loops
for i = 1 to n do
for j = 1 to n do
sum = sum + 1
n n
1 n n
n 2
j 1
i 1 i 1
Asymptotic Analysis CSE 326 Autumn 2001 20
Dependent Nested Loops
for i = 1 to n do
for j = i to n do
sum = sum + 1
n n n n n
1
i 1 j i i 1
(n i 1) (n 1) i
i 1 i 1
n(n 1) n(n 1)
n(n 1) n2
2 2
Asymptotic Analysis CSE 326 Autumn 2001 21
Recursion
A recursive procedure can often be
analyzed by solving a recursive equation
Basic form:
T(n) =
base case: some constant
recursive case: T(subproblems) + T(combine)
Result depends upon
how many subproblems
how much smaller are subproblems
how costly to combine solutions (coefficients)
Asymptotic Analysis CSE 326 Autumn 2001 22
Sum of Queue
SumQueue(Q)
if ([Link] == 0 )
return 0
else
return [Link]() + SumQueue(Q)
One subproblem
Linear reduction in size (decrease by 1)
Combining: constant (cost of 1 add)
T(0) b
T(n) c + T(n – 1) for n>0
Asymptotic Analysis CSE 326 Autumn 2001 23
Sum of Queue Solution
Equation:
T(0) b
T(n) c + T(n – 1) for n>0
Solution:
T(n) c + c + T(n-2)
c + c + c + T(n-3)
kc + T(n-k) for all k
nc + T(0) for k=n
cn + b = O(n)
Asymptotic Analysis CSE 326 Autumn 2001 24
Binary Search
BinarySearch(A, x)
Search A, a sorted array, for item x
7 12 30 35 75 83 87 90 97 99
One subproblem, half as large
Equation:
T(1) b
T(n) T(n/2) + c for n>1
Asymptotic Analysis CSE 326 Autumn 2001 25
Binary Search: Solution
Equation:
T(1) b
T(n) T(n/2) + c for n>1
Solution:
T(n) T(n/2) + c
T(n/4) + c + c
T(n/8) + c + c + c
T(n/2k) + kc
T(1) + c log n where k = log n
b + c log n = O(log n)
Asymptotic Analysis CSE 326 Autumn 2001 26
