Algorithm Analysis

• Motivation - We want to be able to compare algorithms and choose the best one for a given task

• Scientific Method

• Empirical Analysis

• Mathematical models

  • Case analysis

  • Asymptotic notations

    • Big-Oh

    • Big-Omega

    • Big-Theta

  • tilde notation

• Examples to try analysis on

  • Binary search

  • Linked-list insert, remove, etc

Note

Extended reading Complexity Analysis