cs126 asymptotic analysis

Why is the worst-case running time measured?

• Easier to analyse (as average case would require knowing the input distribution)

• Crucial to applications like games, finance, and robotics

Describe how the ‘Experimental’ approach is used to evaluate the running time of an algorithm.

• Write a program implementing the algorithm

• Run the program with inputs of varying size and composition

• Record the time needed for each of these inputs

• Plot the results

What are the limitations of the Experimental approach?

• It is necessary to implement the algorithm, which may be difficult

• In order to compare two algorithms, the same hardware and software environments must be used

Describe how the ‘Theoretical’ approach is used to evaluate the running time of an algorithm.

• Uses a high-level description of the algorithm instead of an implementation

• Characterizes running time as a function of the input size n, denoted T(n)

• Independent of the hardware/software environment

• Can be performed given pseudocode

What makes a good analysis approach?

• Independent of hardware / software environment

• Does not require actually implementing the algorithm

• Takes into account all possible inputs

What is pseudocode?

• High-level description of an algorithm

• Less detailed than a program

• Hardware / software independant

What does RAM consist of?

A potentially unbounded bank of memory cells, each of which can hold an arbitrary number or character.

Define a memory cell.

• A numbered location in memory

• Accessing any cell takes unit time

Define asymptotic analysis.

• Compares relative growth rates of two (or more) functions/algorithms

• Independent of constant multipliers or low-order effects

How do you perform asymptotic analysis?

• Find the worst case number of primitive operations executed as a function of the input size

• Express this function with Big-O notation

What is Big ‘O’ Notation?

• O(g(n))

• {f(n) : ∃ (constants) c > 0, n₀ ≥ 0 : f(n) ≤ cg(n) ∀n ≥ n₀}

• f(n) is bounded from above by g(n)

• is a set of functions

What is Big ‘Omega’ Notation?

• Ω(g(n))

• iff ∃c, n₀ > 0 : ∀n ≥ n₀, f(n) ≥ cg(n) ≥ 0 

• f(n) is bounded from below by g(n)

What is Big ‘Theta’ Notation?

• ϴ(g(n))

• iff ∃ c₁,c₂,n₀ > 0 : 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n), ∀n ≥ n₀

• f(n) and g(n) have the same asymptotic growth rate

What is little ‘o’ / ‘omega’ notation? {EDIT}

little is strict

What is the rule of sum of functions?

O(f + g) = max(O(f), O(g))

What is the rule of product of functions?

O(f x g) = O(f) x O(g)

What is the growth rate of f(n) and g(n) if lim_n→∞ (f(n) / g(n)) = 0

f(n) = O(g(n))

What is the growth rate of f(n) and g(n) if lim_n→∞(f(n) / g(n)) > 0

f(n) = ϴ(g(n))

What is the growth rate of f(n) and g(n) if lim_n→∞(f(n) / g(n)) = ∞

f(n) = Ω(g(n))

What is the growth rate of f(n) and g(n) if lim_n→∞ (f(n) / g(n)) oscillates.

There is no relation.

a^(b+c)

a^ba^c

a^bc

(a^b)^c

a^b/a^c

a^(b-c)

n^{log n (a)}

a

log_b(xy)

log_bx +  log_by

log_b(x/y)

log_bx - log_by

log_b(x^a)

alog_bx

aⁿ - bⁿ

(a - b)(a^n-1 + a^n-2 b + a^n-3 b² + … + b^n-1)

2ⁿ - 1

1 + 2 + 4 + 8 + … + 2^n-1

Define floor.

largest integer ≤ n

Define ceiling.

smallest integer ≥ n

What is the hierarchy of time costs (ordered by growth rate)?

c → logn → n → nlogn → n² → n³ → 2ⁿ

What is the assumed default base of a log?

2