Big-O Notation

Big O is conceptual. It expresses how quickly an algorithm's runtime grows relative to the input.

Big O represents the worst-case, always. Even if you think what you're looking for is the very first thing in the set, Big O doesn't care ,a loop-based find is still considered O(n). That’s because Big O is just a descriptive way of thinking about the code you’ve written, not the inputs expected.

And here goes the cheat sheet

  • Fetching an item from the list using index or key without looping : O(1)
  • Looping over a set of n items: O(n)
  • A nested loop over n items: O(n^2)
  • A divide and conquer algorithm: O(log n)