Algorithms, Logarithms, and Big O 1/4/17


Introduction

Self-taught developers tend to have a very pragmatic approach to software development. We learnt from projects, tutorials, practical courses, and technical books. There's nothing wrong with that. But, we're missing some of the fundamentals that traditional Computer Science majors get during their coursework.

The goal of this post is to demystify the basic terms and concepts you'll need to understand before we start delving into actual examples of famous algorithms. I'll be going over what exactly algorithms and logarithms are, how to calculate Logarithmic run times, what Big O notation is, and why you should care about all of this.

Algorithms

You'll be relieved to discover that you already know exactly what an algorithm is. Despite sounding kind of exotic, an algorithm is nothing more than a set of instructions. A cooking recipe is an algorithm used to create dinner. Binary Search is an algorithm to find a list element.

XKCD algorithm comic

If you write code, you're in the business of algorithms. To write good code, you'll need to understand algorithm design, and of equal importance, algorithm analysis. Luckily for you, most languages come with built in functions for the most commonly encountered algorithms. In other words, if you ever find yourself implementing Binary Search from scratch, you're doing it wrong.

Mathematical Notation

Unless you were a math major, deciphering mathematical notation can be a huge hurdle. The good news is you're not going to need to for this series. I'll be presenting each of the algorithms and various calculations in pure python code. Here's an example using the Summation symbol (sum over a range of numbers) to illustrate what I'm talking about:

k = 1 4 k 2 = 30

Kind of cryptic, right? Here's a long form equivalent that should make a lot more sense:

12+ 22+ 32+ 42=30

Finally, here's the equivalent (non-idiomatic, for clarity) Python code:

k = 1                 # first addend
addend_limit = k + 4  # range limit for the addend sequence
result = 0

while k < addend_limit:
    result += pow(k, 2)
    k += 1

print(result)         # 30

The point of all this is that while Mathematical Notation is incredibly useful (and in many cases necessary) to clearly describe an algorithm, you won't need to understand it for this article series. If you want to learn more about what all the various symbols mean, wikipedia has you covered. If you want to learn more about why symbols are helpful, read this. If you want to get really heavy, read this.

Logarithms

One of the most common algorithm run times (more on run times in the next section) is Log Time, or Logarithmic Time. The logarithm of a number is the exponent to which another fixed number, the base, must be raised to produce that number1.

In the example above, we raised each of the addend base numbers to the power of 2. The final number in our addend sequence was 4, which when raised to the power of 2 became 16. So log216, is equivalent to asking what number when 2 is raised to it equals 16 (thanks Gabe). The answer to which, is 4.

Python has a log() function in the math package that we can use to do the heavy lifting for us. You'll almost always use log 2 when calculating Logarithmic run times. Here's the code to calculate log216

from math import log

log(16, 2)  # 4

Big O Notation

You probably have an intuitive sense for how fast a function is when you write it. Lots of nested for loops? Probably bad. While intuition and experience are good, determing Big O complexity is even better. If you use third party libraries, you'll often want to know exactly how expensive an imported algorithm is going to be. Even with your own code, calculating execution times and understanding how those times scale is easier with a little math than feeding dozens of differently sized data sets into your algorithm.

When calculating a run time, you'll want to be pessimistic. It's the worst case scenario that's most important. For example, lets say we want to search the following list of alphabetically sorted user names:

users = ['Aaron', 'Becky', 'Chris',
         'Dora', 'Eric', 'Felicia',
         'George', 'Holly', 'Igor',
         'Justine', 'Karl', 'Lisa',
         'Moe', 'Nina', 'Olof',
         'Penny', 'Quentin', 'Rebecca',
         'Steve', 'Tina', 'Umberto',
         'Vicky', 'Walter', 'Xena',
         'Yosef', 'Zoe']

We care about the run time to find "Zoe", not "Aaron". Again, the main thing Big O determines is how well an algorithm will scale. Here's a quick breakdown of some of the most common Big O run times from best to worst with an example operation:

NotationNameScalabityExample
O(1)constantExcellentHash Table (Python Dictionary) Keyword Lookup
O(log n)logarithmicGoodBinary Search
O(n)linearFairSimple Search
O(n * log n)n log-star nBadQuicksort
O(n2)quadraticHorribleSelection Sort
O(n!)factorialThe WorstTraveling Salesman via Brute Force

There are a bunch of other notations, but they aren't as common, wikipedia has you covered if you're interested. This next table illustrates the run time scaling for each of the notations listed above if we were searching the users array, assuming it took one second to process each element:

NotationSeconds to "Chris"Seconds to "Zoe"
O(1)11
O(log n)1.54.7
O(n)326
O(n * log n)4.5122
O(n2)9676
O(n!)6403291461126605635584000000

See why scaling matters? As another quick example to really drive home the point, lets say you had a list of 1 million users with "Zoe" at the end, and a search algorithm that took a second to process each name:

NotationSeconds to Millionth "Zoe"
O(log n)19.93 SECONDS
O(n)11.57 DAYS

I'm not even going to list the rest of the run times, it gets scary. The final thing I'm going to go over in this section is the python code to calculate each Big O growth factor for the main notations I've listed up above. Once you know that, it's just a case of determining how long your algorithm takes to process a single element then multiplying the two results together to get your worst case run time.

from math import log, factorial

# This is our input array
users = ['Aaron', 'Becky', 'Chris',
         'Dora', 'Eric', 'Felicia',
         'George', 'Holly', 'Igor',
         'Justine', 'Karl', 'Lisa',
         'Moe', 'Nina', 'Olof',
         'Penny', 'Quentin', 'Rebecca',
         'Steve', 'Tina', 'Umberto',
         'Vicky', 'Walter', 'Xena',
         'Yosef', 'Zoe']

# Here is how to calculate each notations growth factor
# O(1)
constant_factor = 1  # 1

# O(log n)
logarithmic_factor = log(len(users), 2)  # 4.7

# O(n)
linear_factor = len(users)  # 26

# O(n * log n)
n_log_star_n_factor = len(users) * log(len(users), 2)  # 122

# O(n^2)
quadratic_factor = pow(len(users), 2)  # 676

# O(n!)
factorial_factor = factorial(len(users))  # 403291461126605635584000000L

Conclusion

So, hopefully that helps lay the foundation for the rest of the this series. Once we start going over various algorithms, I'm hoping this post will help things crystallize for you. Good luck! Feel free to hit me up on Twitter or send me a message on LinkedIn if you have any questions!