Big O notation is used to describe or calculate time complexity (worst-case performance)of an algorithm. This post will show concrete examples of Big O notation.
A few things to note
- This article was written with intermediate developers in mind and assumes you already know a bit about time complexity, worst case behavior.
- If this word doesn’t ring a bell, I wrote a comprehensive guide here (free article).
Real-Life Big-O
Many “operations” in real life can help us with finding what the order is. When analyzing algorithms/operations, we often consider the worst-case scenario. What’s the worst that can happen to our algorithm and when does our algorithm need the most instructions to complete the execution? Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.
Let’s assume I am standing in the front of a class of students and one of them has my bag. Here are few scenarios and ways in which I can find my bag and their corresponding order of notation.
O(n) — Linear Time:
Scenario: Only one student in my class who hid my bag knows about it.
Approach: I will have to ask each student individually in the class if they have my bag. If they don’t, I move on to ask the next student.
Worst-Case Scenario: In the worst case scenario, I will have to ask n questions.
Show me the code!
Explanation:
- Here, given an input of size n, the number of steps required is directly related to the amount of data it is processing.
- Single for loops, linear search are examples of linear time
- In above example, an array size/input size increases, time to find desired value also increases.
O(1) — Constant Time
Scenario: Student who hid my bag name is known to me.
Approach : Since I know Joe has my bag, I’ll directly ask him to give it to me.
Show me the code!
Explanation:
- Here, given an input of size n, it only takes a one step for the algorithm to accomplish the task.
- An algorithm takes same time(constant time) to execute irrespective of the amount of data.
- This algorithm is not affected by the array size either.
O(n²) — Quadratic Time:
Scenario: In the entire class, only one student knows on which student desk my bag is hidden.
Approach: I will start questioning each student individually and ask him about all the others students too. If I don’t get the answer from the first student, I will move on to the next one.
Worst-Case Scenario: In the worst case scenario, I will have to ask n2 questions, questioning each student about other students as well.
Show me the code!
Explanation:
- Here, given an input of size n, the number of steps it takes to accomplish a task is square of n.
- Each pass to outer loop O(n) requires going through entire list through the inner-loop.
- Nested for-loops are example of quadratic time as we run a linear operation within other linear operation
O(log n) — Logarithmic time:
Scenario: Here, all the students know who has my bag but will only tell me if I guessed the right name.
Approach: I will divide the class in half, then ask: “Is my bag on the left side, or the right side of the class?” Then I take that group and divide it into two and ask again, and so on.
Worst Case Scenario: In the worst case, I will have to ask log n questions.
Show me the code!
Explanation:
- Here, given an input of size n, the number of steps it takes to accomplish the task are decreased by roughly 50% each time through the algorithm.
- O (log N) algorithms are very efficient because increasing amount of data has little effect at some point early on because the amount of data is halved on each run through.
- Binary search is a perfect example of this.
Closing Notes:
Thanks for reading! I publish things I learn daily every single weekday here or you can follow me on Twitter .
Here are some helpful resources to learn more:
Top comments (3)
Just started learning about the concept of "Big O" and this came up as I was searching for "real world examples" of this. Thanks for creating this example!!
What's going on here?
dev-to-uploads.s3.amazonaws.com/i/...
Good day Shilpa Jain, it seems like this link is broken: jshilpa.com/the-ultimate-beginners... . Thank you for this great article