Skip to content

Instantly share code, notes, and snippets.

@thejoycekung

thejoycekung/Big O.md

Created August 5, 2017 16:11
Show Gist options
  • Save thejoycekung/6cfea978c699af951446b8082d6721bf to your computer and use it in GitHub Desktop.
Save thejoycekung/6cfea978c699af951446b8082d6721bf to your computer and use it in GitHub Desktop.
Download ZIP
Raw
Big O.md

O(n^n) > O(n!) > O(2^n) > O(n^2) > O(n log n) > O(n) >> O(log n)

O(log n) --> good example is binary search; elements to search gets halved each time (in perfect scenario)

For recursive functions, draw out the tree of function calls --> often is O(branches^depth) --> space complexity is O(n) though, only O(n) nodes exist at any point

Be careful of when your n is ever-shifting (ahem, many recursive problems)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment