Computer Science Fundamentals for Self-Taught Programmers

Justin Abrahms

Resources

• The Algorithm Design Manual
  • Steven S. Skiena
  • http://algorist.com
• Algorithms: Design and Analysis, Part 1
  • Coursera
  • https://www.coursera.org/course/algo
• Computer Science for Self-Taught Programmers
  • Justin Abrahms (this speaker)

Big-O notation

• O(1)
  • array lookup
• O(n)
  • for-loop over every item
• O(log n)
  • binary search
  • Is 4 in the list range(11), which is sorted?
  • Is 4 > 6? No, ignore the last half of the list
  • Is 4 > 3? Yes, ignore the first half of the remainder
  • ...
• O(n^2)
  • nested for-loop
• Gotchas
  • The Big-O of a function might not matter...
  • Theoretical speed is different than practical speed.
  • This is probably not going to make your app faster
• Recap
  • Useful in communicating about complexity of code
  • basic arithmetic and algebra
  • used in talking about data structures and algorithms