Back to the Basics: Algorithmic complexity (Big O)

Date Created
Sep 6, 2022 03:55 PM
Date Published
Sep 12, 2022
This is more of a note-taking space right now. I’m following along
lanepartonUpdated Sep 7, 2022

Algorithmic complexity / Big-O / Asymptotic analysis

  • Nothing to implement here, you're just watching videos and taking notes! Yay!
  • There are a lot of videos here. Just watch enough until you understand it. You can always come back and review.
  • Don't worry if you don't understand all the math behind it.
  • You just need to understand how to express the complexity of an algorithm in terms of Big-O.
Harvard CS50 - Asymptotic Notation (video)
  • O(n) = linear complexity
  • O(1) = constant complexity
  • O(log n) = logarithmic complexity
  • Ω = Best case constant
  • Θ = best and worst case scenarios are the same
  • Binary Search -
    • Starts in the middle
    • If > checks left
    • If > checks right
    • Repeat…
Big O Notations (general quick tutorial) (video)
  • Measure how well a computer algo scales as the amount of data increases
    • 10 element array vs 10,000 element array
    TopCoder (includes recurrence relations and master theorem):