Big O Notation
Tags: spacecomplexity, bigonotation, bigo, computerscience
Published: 2021-06-15 03:09:28

---
title: Big O Notation
published: true
date: 2020-10-15 00:00:00 UTC
tags: spacecomplexity,bigonotation,bigo,computerscience
canonical_url: https://jay-cruz.medium.com/big-o-notation-e4d625021596
---

![Image of O and n Scrabble game squares](https://cdn-images-1.medium.com/max/1024/1*qd8nCWNN7ne8VxUTedCrpA.jpeg)

### What is Big O?

Big O notation is a mathematical tool commonly used in Computer Science for measuring the runtimes of computer algorithms and describing their complexity. It’s often used to determine what the efficiency of a particular approach to a problem will be. More specifically, Big O determines what the “worst-case scenario” is for an algorithm’s runtime and space as the input size grows.

### Time Complexity

Instead of measuring the actual time of an algorithm, we use time complexity which is the method of determining how many times an algorithm’s statements will run.

### Most common time complexities

_The n in O() represents the input size._

**O(1)** — Constant runtime. This means the code executes instantly. No matter what the input size it executes in the same exact time. For example, if a group of programmers all decide to say hello world at the same time it would cost the same amount of time as only one programmer saying hello world. The following code executes in constant time:

{% gist https://gist.github.com/CoderJay06/aa65c70e6083edfd7a39123d4dd3d0e7 %}

**O(n)** — Linear runtime. Linear means to execute n amount of times. For example, if you can picture a long line of programmers standing in line for a job interview. Say you need to find out all of their names. You would go and ask each programmer their name individually. The following code executes in linear time:

{% gist https://gist.github.com/CoderJay06/898652a00770000242b47f2bdc6e1384 %}

**O(n²)** — Quadratic time. Quadratic means the runtime number of executions increases in relation to the square root of n. This is not an ideal runtime as it will only grow as the input size increases. An example in code would be nested for loop as follows:

{% gist https://gist.github.com/CoderJay06/3d2176a1fb8c3ea9338179a0c81d59ea %}

**O(log n)** — Logarithmic time. This means the runtime will increase in relation to the logarithm of n (the input size). A real-world example of this runtime would be searching a phonebook for a specific number. You open the phonebook halfway then if you don't find it, repeat the process of halving the pages of only the section that needs to be checked until you eventually find the number you’re looking for. This would be considered [binary search](https://en.wikipedia.org/wiki/Binary_search_algorithm), which is a common algorithm that runs in logarithmic time. _Learn more about logarithms_ [_here_](https://www.khanacademy.org/math/algebra2/x2ec2f6f830c9fb89:logs)

{% gist https://gist.github.com/CoderJay06/a3f205f91c720ed0ee38ccdbfc34b54c %}

### Drop the Constants and Non-Dominant Terms

When determining a Big O notation runtime, the constants should be dropped. For example, if you have a specific runtime expression _O(n + 1 + 1 + 1)_ this would be boiled down to _O(n)_ because Big O only describes the worst-case and including the constants wouldn’t make a big enough difference. Also, non-dominant terms should be dropped from the expression, for example, _O(n² + n)_ would become _O(n²)_

### Space Complexity

In Big O space complexity describes the total amount of memory space used by an algorithm determined by its input size n. This is also expressed the same as time complexity for example an array of size n elements would be expressed as _O(n)_ space.

### Analyzing Space Complexity

{% gist https://gist.github.com/CoderJay06/81b8d310ac0bb5b5f9322e43d81f4348 %}

To determine the space complexity of this code, we can list the size in bytes of the variables used.  
_int = 4 bytes, double = 8 bytes_

The space for this example code would be measured by 4n + 4 + 8 + 4. Since n is dominant this would evaluate to O(n) space. _Read more about Space Complexity_ [_here_](https://www.baeldung.com/cs/space-complexity)

#### Additional Big O Resources

[https://en.wikipedia.org/wiki/Big\_O\_notation](https://en.wikipedia.org/wiki/Big_O_notation)

[What is Big O Notation Explained: Space and Time Complexity](https://www.freecodecamp.org/news/big-o-notation-why-it-matters-and-why-it-doesnt-1674cfa8a23c/)

[https://www.geeksforgeeks.org/understanding-time-complexity-simple-examples/](https://www.geeksforgeeks.org/understanding-time-complexity-simple-examples/)

_Originally published at_ [_https://coderjay06.github.io_](https://coderjay06.github.io/big_o_notation) _on October 15, 2020._