Algorithm

Algorithm

Criteria

- Structure (simplicity, easy to read ....)

- Running time

- Memory

- else

Focusing on worst case running time: easy to analyze, critical

Running time: function of input size n

Random Access Model: CPU

Pseudocode: High-level description of algorithm

for ... do ...

←(assignment), =(==), n²(mathematical format)

Primitive Operators

Big Oh

f(n) = O(g(n)): g(n) asymptotically greater than or equal to f(n)

rules: 1. use the smallest possible g(n) (e.g. 3n+1 = O(n), not O(nⁿ))

        2. use the simplest expression   (e.g. 3n+1 = O(n), not O(3n))

Asymptotic Analysis

1. Find worst case f(n)

2. Find g(n) such that f(n) = O(g(n))

f(n) = Ω(g(n)): g(n) asymptotically less than or equal to f(n)

f(n) = Θ(g(n)): g(n) asymptotically equal to g(n) 

Quiz: Is assignment primitive?