Big-O Notation — Learning Through Examples
Tags: programming, computerscience, coding, softwaredevelopment
Published: 2018-03-24 16:15:29

---
title: "Big-O Notation — Learning Through Examples"
published: true
tags: programming,computer-science,coding,software-development
canonical_url: https://jshilpa.com
---

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.

![](https://cdn-images-1.medium.com/max/652/1*PeVXl5ZQ0rSmDik86Zlt2g.jpeg)<figcaption>After discovering that complexity of the algorithm won’t be taken into consideration on the exam. (Source: <a href="https://www.reddit.com/r/ProgrammerHumor/comments/7jty1d/after_discovering_that_complexicity_of_the/">Reddit</a>)</figcaption>

**A few things to&nbsp;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).](https://jshilpa.com/the-ultimate-beginners-guide-to-analysis-of-algorithm/)

### 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&nbsp;Time:

**Scenario:** Only one student in my class who hid my bag knows about&nbsp;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&nbsp;student.

**Worst-Case Scenario:** In the worst case scenario, I will have to ask _n_ questions.

**Show me the&nbsp;code!**

{% gist https://gist.github.com/JShilpa/0e784cdcab7444aa65caffa6671e756d %}

**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&nbsp;time
3. In above example, an array size/input size increases, time to find desired value also increases.

### O(1) — Constant&nbsp;Time

**Scenario:** Student who hid my bag name is known to&nbsp;me.

**Approach** : Since I know _Joe_ has my bag, I’ll directly ask him to give it to&nbsp;me.

**Show me the&nbsp;code!**

{% gist https://gist.github.com/JShilpa/ee8ce0ab98b7ed1b2f778f49258310c9 %}

**Explanation:**

1. Here, given an input of size n, it only takes a one step for the algorithm to accomplish the&nbsp;task.
2. An algorithm takes same time(constant time) to execute irrespective of the amount of&nbsp;data.
3. This algorithm is not affected by the array size&nbsp;either.

### O(n²) — Quadratic Time:

**Scenario:** In the entire class, only one student knows on which student desk my bag is&nbsp;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&nbsp;one.

**Worst-Case Scenario:** In the worst case scenario, I will have to ask _n2_ questions, questioning each student about other students as&nbsp;well.

**Show me the&nbsp;code!**

{% gist https://gist.github.com/JShilpa/5a107da0a14fd139378fe754ffcdcc99 %}

**Explanation:**

1. Here, given an input of size n, the number of steps it takes to accomplish a task is square of&nbsp;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&nbsp;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&nbsp;on.

**Worst Case Scenario:** In the worst case, I will have to ask _log n_ questions.

**Show me the&nbsp;code!**

{% gist https://gist.github.com/JShilpa/d31732e29d7bab9a29a8dbf730c109e2 %}

**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&nbsp;through.
3. Binary search is a perfect example of&nbsp;this.

### Closing Notes:

Thanks for reading! I publish things I learn daily every [**single weekday here**](https://jshilpa.com) or you can follow me on&nbsp;[**Twitter**](https://twitter.com/JainShilpa26) **.**

Here are some helpful resources to learn&nbsp;more:

- [Wikipedia](https://en.wikipedia.org/wiki/Time_complexity)
- [Big O Cheat&nbsp;Sheet](http://bigocheatsheet.com/)

* * *