Big O Notation: The Basics

One of the fundamental concepts in computer science and programming is something called “Big O Notation”. In this blog, I’ll be going over what Big O is, why it is important when it comes to programming, and various examples of Big O.

Big O and bagels
Big O, bagel, same thing, right?

What is Big O Notation?

Importance of Big O

Calculating Big O

Calculating…
Calculating…

Before we get to calculating the Big O of computer programs, we need to know how to calculate the Big O of algorithms in general. Bear with me as I bring out some algebra.

If there’s one thing to remember when it comes to calculating the Big O of an algorithm, it is that we are only concerned with the part that will take the longest. Why is this? Consider the following function:

T(n) = 6n² + 3n — 5

As n approaches infinity, the n² term will dominate, and make it so that all the other terms can be disregarded. For example, when n = 1000, the 6n² term is 2000 times as large as the 3n term (6(1000)² = 6,000,000 while 3(1000) = 3,000). In general, as we approach infinity, ignoring the 3n term will have basically no effect on the outcome of the function. In addition, we can remove any coefficients in the function for the same reason. If F(n) =1,000,000n², and G(n) = n³, the output of G(n) will eventually exceed the output of F(n) once n passes a certain threshold (that being n =1,000,000). So after only taking the most dominant term, and removing all coefficients, we can say that the Big O of the function T(n) = 6n² + 3n — 5 is n². Often, you may see this written as:

T(n) = O(n²)

but this is misleading because “=” is not meant to express “is equal to”, but rather just “is”. A more accurate expression would use the “∈” symbol from set notation, so we would write:

T(n) ∈ O(n²)

Now lets apply this to programming, and I’ll show you the various runtimes of different, common algorithms.

Constant Time: O(1)

  • Accessing a specific element in an array:
def get_array_index(arr, idx)
arr[idx]
end
  • Determining whether a number is even or odd:
def even_or_odd(n)
n % 2 == 0
end

Logarithmic Time: O(log n)

def binary_search(arr, n)    
first = 0
last = arr.length - 1
while first <= last
i = (first + last) / 2
if arr[i] == n
return true
elsif arr[i] > n
last = i - 1
elsif arr[i] < n
first = i + 1
else
return false
end
end
end

Linear Time: O(n)

def linear_search(arr, n)
for i in 0..arr.length
if arr[i] == n
return true
end
end
false
end

Quadratic Time: O(n²)

def quadratic_time(arr)
for i in 0..arr.length
for j in arr[i].length
puts arr[i][j]
end
end
end

Here are various runtimes, listed from most efficient to least efficient:

  • O(1)
  • O(log log n)
  • O(log n)
  • O(n)
  • O(n log* n)
  • O(n²)
  • O(nª), a > 2
  • O(n!)

The Big Deal

Hope this helps!

Thanks for reading!
Thanks for reading!
Source: K-On!

Software engineering student at Flatiron School. Loves all things gaming, photography, and anime.