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

1. This article was written with intermediate developers in mind and assumes you already know a bit about time complexity, worst case behavior.
2. 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:

1. Here, given an input of size n, the number of steps required is directly related to the amount of data it is processing.
2. Single for loops, linear search are examples of linear time
3. 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:

1. Here, given an input of size n, it only takes a one step for the algorithm to accomplish the task.
2. An algorithm takes same time(constant time) to execute irrespective of the amount of data.
3. 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:

1. Here, given an input of size n, the number of steps it takes to accomplish a task is square of n.
2. Each pass to outer loop O(n) requires going through entire list through the inner-loop.
3. 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:

1. 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.
2. 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.
3. 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:

• Wikipedia
• Big O Cheat Sheet