CSE373: Data Structures and Algorithms

Lecture 4: Asymptotic Analysis

Aaron Bauer
Winter 2014
Previously, on CSE 373

•  We want to analyze algorithms for efficiency (in time and space)

•  And do so generally and rigorously
–  not timing an implementation
•  We will primarily consider worst-case running time
•  Example: find an integer in a sorted array
–  Linear search: O(n)
–  Binary search: O(log n)
–  Had to solve a recurrence relation to see this

Winter 2014 CSE373: Data Structure & Algorithms 2

Another example: sum array
Two “obviously” linear algorithms: T(n) = O(1) + T(n-1)

int sum(int[] arr){

Iterative: int ans = 0;
for(int i=0; i<arr.length; ++i)
ans += arr[i];
return ans;
}

Recursive: int sum(int[] arr){

return help(arr,0);
–  Recurrence is }
k+k +…+k int help(int[]arr,int i) {
if(i==arr.length)
for n times return 0;
return arr[i] + help(arr,i+1);
}
Winter 2014 CSE373: Data Structure & Algorithms 3
What about a binary version?
int sum(int[] arr){
return help(arr,0,arr.length);
}
int help(int[] arr, int lo, int hi) {
if(lo==hi) return 0;
if(lo==hi-1) return arr[lo];
int mid = (hi+lo)/2;
return help(arr,lo,mid) + help(arr,mid,hi);
}

Recurrence is T(n) = O(1) + 2T(n/2)

–  1 + 2 + 4 + 8 + … for log n times
–  2(log n) – 1 which is proportional to n (definition of logarithm)

Easier explanation: it adds each number once while doing little else

“Obvious”: You can’t do better than O(n) – have to read whole

array
Winter 2014 CSE373: Data Structure & Algorithms 4
Parallelism teaser
•  But suppose we could do two recursive calls at the same time
–  Like having a friend do half the work for you!
int sum(int[]arr){
return help(arr,0,arr.length);
}
int help(int[]arr, int lo, int hi) {
if(lo==hi) return 0;
if(lo==hi-1) return arr[lo];
int mid = (hi+lo)/2;
return help(arr,lo,mid) + help(arr,mid,hi);
}

•  If you have as many “friends of friends” as needed the recurrence

is now T(n) = O(1) + 1T(n/2)
–  O(log n) : same recurrence as for find

Winter 2014 CSE373: Data Structure & Algorithms 5

Really common recurrences

Should know how to solve recurrences but also recognize some

really common ones:

T(n) = O(1) + T(n-1) linear

T(n) = O(1) + 2T(n/2) linear
T(n) = O(1) + T(n/2) logarithmic
T(n) = O(1) + 2T(n-1) exponential
T(n) = O(n) + T(n-1) quadratic (see previous lecture)
T(n) = O(n) + 2T(n/2) O(n log n)

Note big-Oh can also use more than one variable

•  Example: can sum all elements of an n-by-m matrix in O(nm)

Winter 2014 CSE373: Data Structure & Algorithms 6

Asymptotic notation

About to show formal definition, which amounts to saying:

1.  Eliminate low-order terms
2.  Eliminate coefficients

Examples:
–  4n + 5
–  0.5n log n + 2n + 7
–  n3 + 2n + 3n
–  n log (10n2 )

Winter 2014 CSE373: Data Structure & Algorithms 7

Big-Oh relates functions

We use O on a function f(n) (for example n2) to mean the set of

functions with asymptotic behavior less than or equal to f(n)

So (3n2+17) is in O(n2)
–  3n2+17 and n2 have the same asymptotic behavior

Confusingly, we also say/write:

–  (3n2+17) is O(n2)
–  (3n2+17) = O(n2)

But we would never say O(n2) = (3n2+17)

Winter 2014 CSE373: Data Structure & Algorithms 8

Big-O, formally

Definition:
g(n) is in O( f(n) ) if there exist constants
c and n0 such that g(n) ≤ c f(n) for all n ≥ n0

•  To show g(n) is in O( f(n) ), pick a c large enough to “cover the

constant factors” and n0 large enough to “cover the lower-order
terms”
–  Example: Let g(n) = 3n2+17 and f(n) = n2
c=5 and n0 =10 is more than good enough

•  This is “less than or equal to”

–  So 3n2+17 is also O(n5) and O(2n) etc.

Winter 2014 CSE373: Data Structure & Algorithms 9

More examples, using formal definition

•  Let g(n) = 1000n and f(n) = n2

–  A valid proof is to find valid c and n0
–  The “cross-over point” is n=1000
–  So we can choose n0=1000 and c=1
•  Many other possible choices, e.g., larger n0 and/or c

Definition:
g(n) is in O( f(n) ) if there exist constants
c and n0 such that g(n) ≤ c f(n) for all n ≥ n0

Winter 2014 CSE373: Data Structure & Algorithms 10

More examples, using formal definition

•  Let g(n) = n4 and f(n) = 2n

–  A valid proof is to find valid c and n0
–  We can choose n0=20 and c=1

Definition:
g(n) is in O( f(n) ) if there exist constants
c and n0 such that g(n) ≤ c f(n) for all n ≥ n0

Winter 2014 CSE373: Data Structure & Algorithms 11

What’s with the c

•  The constant multiplier c is what allows functions that differ only

in their largest coefficient to have the same asymptotic
complexity
•  Example: g(n) = 7n+5 and f(n) = n
−  For any choice of n0, need a c > 7 (or more) to show g(n) is
in O( f(n) )

Definition:
g(n) is in O( f(n) ) if there exist constants
c and n0 such that g(n) ≤ c f(n) for all n ≥ n0

Winter 2014 CSE373: Data Structure & Algorithms 12

What you can drop

•  Eliminate coefficients because we don’t have units anyway

–  3n2 versus 5n2 doesn’t mean anything when we have not
specified the cost of constant-time operations (can re-scale)

•  Eliminate low-order terms because they have vanishingly small

impact as n grows

•  Do NOT ignore constants that are not multipliers

–  n3 is not O(n2)
–  3n is not O(2n)

(This all follows from the formal definition)

Winter 2014 CSE373: Data Structure & Algorithms 13

Big-O: Common Names (Again)

O(1) constant (same as O(k) for constant k)

O(log n) logarithmic (probing)
O(n) linear (single-pass)
O(n log n) “n log n” (mergesort)
O(n2) quadratic (nested loops)
O(n3) cubic (more nested loops)
O(nk) polynomial (where is k is any constant)
O(kn) exponential (where k is any constant > 1)

Winter 2014 CSE373: Data Structure & Algorithms 14

Big-O running times

•  For a processor capable of one million instructions per second

Winter 2014 CSE373: Data Structure & Algorithms 15

More Asymptotic Notation

•  Upper bound: O( f(n) ) is the set of all functions asymptotically

less than or equal to f(n)
–  g(n) is in O( f(n) ) if there exist constants c and n0 such that
g(n) ≤ c f(n) for all n ≥ n0

•  Lower bound: Ω( f(n) ) is the set of all functions asymptotically

greater than or equal to f(n)
–  g(n) is in Ω( f(n) ) if there exist constants c and n0 such that
g(n) ≥ c f(n) for all n ≥ n0

•  Tight bound: θ( f(n) ) is the set of all functions asymptotically

equal to f(n)
–  Intersection of O( f(n) ) and Ω( f(n) ) (use different c values)

Winter 2014 CSE373: Data Structure & Algorithms 16

Correct terms, in theory
A common error is to say O( f(n) ) when you mean θ( f(n) )
–  Since a linear algorithm is also O(n5), it’s tempting to say “this
algorithm is exactly O(n)”
–  That doesn’t mean anything, say it is θ(n)
–  That means that it is not, for example O(log n)

Less common notation:

–  “little-oh”: intersection of “big-Oh” and not “big-Theta”
•  For all c, there exists an n0 such that… ≤
•  Example: array sum is o(n2) but not o(n)
–  “little-omega”: intersection of “big-Omega” and not “big-Theta”
•  For all c, there exists an n0 such that… ≥
•  Example: array sum is ω(log n) but not ω(n)
Winter 2014 CSE373: Data Structure & Algorithms 17
What we are analyzing

•  The most common thing to do is give an O or θ bound to the

worst-case running time of an algorithm

•  Example: binary-search algorithm

–  Common: θ(log n) running-time in the worst-case
–  Less common: θ(1) in the best-case (item is in the middle)
–  Less common: Algorithm is Ω(log log n) in the worst-case
(it is not really, really, really fast asymptotically)
–  Less common (but very good to know): the find-in-sorted-
array problem is Ω(log n) in the worst-case
•  No algorithm can do better
•  A problem cannot be O(f(n)) since you can always find a
slower algorithm, but can mean there exists an algorithm

Winter 2014 CSE373: Data Structure & Algorithms 18

Other things to analyze

•  Space instead of time

–  Remember we can often use space to gain time

•  Average case
–  Sometimes only if you assume something about the
probability distribution of inputs
–  Sometimes uses randomization in the algorithm
•  Will see an example with sorting
–  Sometimes an amortized guarantee
•  Average time over any sequence of operations
•  Will discuss in a later lecture

Winter 2014 CSE373: Data Structure & Algorithms 19

Summary

Analysis can be about:

•  The problem or the algorithm (usually algorithm)

•  Time or space (usually time)

–  Or power or dollars or …

•  Best-, worst-, or average-case (usually worst)

•  Upper-, lower-, or tight-bound (usually upper or tight)

Winter 2014 CSE373: Data Structure & Algorithms 20

Usually asymptotic is valuable

•  Asymptotic complexity focuses on behavior for large n and is

independent of any computer / coding trick

•  But you can “abuse” it to be misled about trade-offs

•  Example: n1/10 vs. log n

–  Asymptotically n1/10 grows more quickly
–  But the “cross-over” point is around 5 * 1017
–  So if you have input size less than 258, prefer n1/10
•  For small n, an algorithm with worse asymptotic complexity
might be faster
–  Here the constant factors can matter, if you care about
performance for small n

Winter 2014 CSE373: Data Structure & Algorithms 21

Timing vs. Big-Oh Summary

•  Big-oh is an essential part of computer science’s mathematical

foundation
–  Examine the algorithm itself, not the implementation
–  Reason about (even prove) performance as a function of n

•  Timing also has its place

–  Compare implementations
–  Focus on data sets you care about (versus worst case)
–  Determine what the constant factors “really are”

Winter 2014 CSE373: Data Structure & Algorithms 22