Big O Notation

Algorithms and Data Structures From Zero to Hero

Sea turtle black and white illustration

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.

array of 100 elements from 1 to 100
Steps that takes the binary search in an array of 1 to 100. (7)

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.

Times simple search vs binary search
O refers to Big O and (n) number of operations

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).

Function that do two step first one in O(a) and second one in O(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.

Function that do 2 step first one in O(n) and second one in O(n^2)

The Graph

Big O graph
Source: Wikipedia

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).

--

--

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kemil Beltre

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