# An Intro to Time Complexity & Big-O Notation

## A beginner’s guide to assessing and describing algorithm run time.

Y**ou’ve started a course/book/class/whatever on data structures and algorithms, and your brain is melting**. Before you can even get to the meat — or the mushroom — you’re hit with “*big-o notation*” this and “*time/space complexity*” that. Here’s my attempt to break it down into “I-don’t-have-a-computer-science-degree-or-a-math-brain” terms.

# What the [insert expletive] is time complexity and big-O notation?

**Time complexity** is the amount of time taken for an algorithm to run as a function of the number of operations performed to complete the task. The fewer the number of operations, the more efficient the algorithm in terms of time complexity. There also exists a relationship between the number of operations and the input data size (n).

**Big-O Notation **describes the run time of an algorithm in terms of growth in the number of operations in relation to input size (n). The given notation is written: **O[n]**, where O is the order of growth and n is the number of operations.

# Sounds cool, but how do we evaluate how fast an algorithm runs?

Let’s start with an algorithm to perform the following: G*iven positive integer n, print out all integers from 1 to n.*

Consider the input. What happens when *n* huge?

*If n = 1. 1 number is printed.*

*If n = 10. 10 numbers are printed.*

*If n = 100. 100 numbers are printed.*

As *n* increases, so do the number of print statements. In this case, the number of print statements increases linearly with an increase in *n*. In big-O notation, this algorithm runs with **O(n)** time complexity where *n* is the input integer.

## Let’s add a print statement before the loop. How does that change the time complexity?

Here’s our updated algorithm:

It’s the same **O(n)**. But why? **The new line of code is not dependent on input size.** The number of print statements that occur could be expressed as n + 1, *but *when expressed in big-O notation (remember it’s a generalization), we care only about the most dominant part of the algorithm. In this case, only the loop is dependent on the input size.

**Note:** BIG-O SHOULD DESCRIBE THE MOST DOMINANT PART OF THE ALGORITHM*****

Time to mix it up again.

## How does the time complexity change if we add a loop to print number 1 to *n* a second time?

*Given positive integer n, print out all integers from 1 to n. Twice.*

Now there are *n* + *n* number of print statements, or 2*n*. The number of print statements is still increasing linearly with *n,* so the big-O of this algorithm is still **O(n)**.

**Note:** DROP THE COEFFICIENTS**

## What is the time complexity of the following summation algorithm?

*Given a positive integer, return the sum from 1 to n.*

**O(n)** again. OK — this is the last time I’ll do that, I promise! So, why does it also have a time complexity of O(n)? The loop runs *n* times, adding the value of the current number to the total for all numbers from 1 to *n*.

## How do we make it more time-efficient?

The following code also returns the sum from 1 to *n*.

The above algorithm has a constant time complexity of **O(1)** because it runs the same amount of time regardless of the input size.

**Code with O(1) time complexity**

- Declaring a variable

`const variable = 100;`

2. Print statement

`console.log("hello world")`

3. Loop for a constant value

`for(i = 0; i < 3; i++) {`

console.log(i)

}

The last example is coming right up!

*Given n that represents the length of a square grid, print all the coordinates of the grid.*

What is the time complexity of this algorithm? We have a loop within a loop which means if *n* = 4, the print will execute *n *x* n* times or 16 times. The big-O of this algorithm is **O(n^2)**. The time complexity is scaling quadratically. In other words, for every iteration of the outer loop, we need to iterate another *n* number of times (the inner loop).

We’ve looked at constant, **O(1)**, linear, **O(n)**, and quadratic, **O(n^2)** time complexity (fastest to slowest). Here are some other runtimes, from slowest to fastest:

- O(n!) - factorial
- O(2n) - exponential
- O(n^2) - quadratic
- O(nlogn) - nlogn
- O(n) - linear
- O(logn) - logarithmic
- O(1) - constant

Maybe we’ll get to those in future posts. Thanks for reading!

# The Little Extras

*The most dominant part of the algorithm will describe whether it is asymptotically equivalent — i.e., essentially equal. In the case of big-o, this means that with an increase in the input size, be it *n* and *n + 1, *the rate increase will be the same for both.

**Coefficient: the numeric factor of a term, e.g., the coefficient of 3x is 3, the coefficient of 2n is 2.