# Big-O Notation — Learning Through Examples

###
Shilpa Jain
*
Originally published at
jshilpa.com
on
*
・4 min read

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:

Make better choices about your code and your career.

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