# Big O Notation

## Terminology

The letter O is used because it describes the run time as being on the Order of something, which is a mathematician’s way of saying that two things grow similarly.

## What is “Notation” mean?

A notation is a collection of related symbols that are each given an arbitrary meaning, created to facilitate structured communication within a domain of knowledge or field of study.

## What is NOT Big O?

With Big O, we don’t measure the speed of an algorithm in seconds (or minutes). We measure the rate of growth of an algorithm in the number of operations it takes to complete.

## Time and Space Complexity

Time complexity: This is what the concept of asymptotic runtime, or big O time, means.

## Binary search

Suppose you’re searching for a word in a dictionary. The word starts with Ka. You could start at the beginning and keep flipping pages until you get to the Ka, But you’re more likely to start at a page in the middle because you know the Ka is going to be near the middle of the dictionary.

## Algorithm running times grow at different rates

Ada is writing a search algorithm for NASA. Her algorithm will kick when a rocket is about to land on the Moon, and it will help calculate where to land.

## Some common Big O run times

Here are five Big O run times that you’ll encounter a lot, sorted from fastest to slowest:

• O(log n), also known as log time. Example: Binary search.
• O(n), also known as linear time. Example: Simple search.
• O(n * log n). Example: A fast sorting algorithm, like quicksort.
• O(n²). Example: A slow sorting algorithm, like selection sort.
• O(n!). Example: A really slow algorithm, like the traveling salesperson.

# 4 Important Rules to Understand Big O

## 1. Different steps get Added

This means if have two different steps in your algorithms you add up steps. So if you have a first step that takes O(a) and a second step that takes O(b) you would up those run times and you get O(a+b).

## 2. Drop Constants

Suppose that we want to print the min and the max element of an array, there are many way, in this case, we have two:

## 3. Different inputs -> Different Variables

Big O is an equation that expresses how runtime changes, and how its scales.

## 4. Drop non-dominate terms

What this simply means is when you have different blocks running at different times the Big O should be the worst scenario.

## EXERCISES

Give the run time for each of these scenarios in terms of Big O.

1. Suppose you have a sorted list of 136 names, and you’re through it using binary search. What’s the maximum number of steps it would take?
2. Suppose you double the size of the list. What’s the maximum number of steps now?
3. You have a name, and you want to find the person’s phone number in the phone book.
4. You want to read the numbers of every person in the phone book.
5. You want to read the numbers of just the As.

## Recap

• Drop the non-dominate terms, Big O establishes a worst-case time.
• Drop constants, you are looking for how things scale roughly.
• O(log n) is faster than O(n), but it gets a lot faster once the list of items you’re searching through grows
• Algorithm speed isn’t measured in seconds.
• Algorithms times are measured in terms of the growth of an algorithm.
• Algorithms times are written with Big O notation.

## References:

• Wikipedia
• Grokking Algorithms (book).
• Cracking the coding interviews (book).

--

--

## More from Kemil Beltre

Sometimes I write about technical topics and sometimes about what I feel like.