O(log n): Logging time

If you're following this series, we've already covered constant, linear and exponential time. Now it's time to get logarithmic!

If you don't remember what the logarithm is from high school, that's perfectly fine. I'm not the best at them either. In fact, in math class you probably dealt with logs with a base 10 (since most math uses the decimal system as default), but I'm going to be talking about base 2 (for other that will make sense in a bit).

A good compromise for our catering company

After all that work teaching the haters a lesson, It's time for our algorithmic catering company to get back to catering.

The problem is, making our O(n) individual meals was too hard, and our O(1) soup got complaints for being too boring. We need something in the middle; something less complex than linear time, but that solves a problem that can't be solved in constant time.

What about a buffet?

Instead of making individual meals for every person, or making one big meal for everyone, we could do our events buffet style. That way, people could get the individual meals they want, but we wouldn't have to make a meal for everyone, just several big trays.

It would probably be a good idea to increase the variety of foods, depending on the size of the event. The more people, the more likely someone will complain that we didn't have what they want. We also charge more money for larger events, so we need to give them their money's worth.

At the same time, if we add a new dish for every person, that would defeat the point. What we could do, is add a new dish every time the number of guests doubles!

Think about it, for a party of 10 people (assuming we start with one dish for one person) we would make 4 dishes*. That seems like a good amount for 10 people, and once we get 16 we'll make a 5th dish. Those are reasonable numbers, and still less work than individual meals.

What about 1,000 guests? If you work it out, we'd only have to make 11 dishes! That's way less work, and I doubt anyone would complain with over 10 options on the menu.

Great!

Putting some Logarithm in our Algorithm

In order for our plan to work, we'll need to find a way to increase our dishes by one whenever our total doubles. Another way to think of it, is that we need to find the number of times the number of guests can be divided in half until you get to one. This is also the exponent that 2 would be raised to to get to our number of guests.

If it hasn't come back to you yet, this is exactly what logarithm is for! Specifically, we need to use log base 2 because our doubling/multiplying by 2 means that 2 is the number with the exponent.

With all that in mind, let's make some pseudocode for our new catering algorithm:

# n = number of guests

def cater_party_buffet_style(n)

   number_of_dishes = 1 #set a default number of dishes

   if n == 0
      # if no one shows up, we don't have to cook
      number_of_dishes = 0
   elsif n < 4
      # if we have less than 4 guests (but at least one)
      # we should just make 2 dishes.
      number_of_dishes = 2
   else
      # We use log base 2 to get our exact number of dishes
      # And we use `ceil` to round up 

      number_of_dishes = Math.log(n, 2).ceil
   end

   number_of_dishes.times do 
      cook_something(entrée, side, dessert, etc)
   end
end

O(log n) complexity

Looking at our algorithm, it's pretty easy to see how the number of operations grows. Since it clearly increases with the logarithm (base 2) of the input, we say it is O(log n) or logarithmic time.

Probably the most famous example of a O(log n) time complexity algorithm is binary search. I'm not going to go over it, because it's been done to death, but here's a good resource.

The key to logarithmic time is that as the input size increases, the number of operations increases at an increasingly smaller rate.

When we look at logarithmic time curve on a chart, we can see that at low values it's relatively similar to linear time. But as our input size increases, it is actually causes actually gets closer to constant time.

Final Notes

If the giveaway for linear time is "iterating over the input", and for exponential time it's "nested iteration", then what's the giveaway for logarithmic time?

We could say: "removing a fractional part of the data set with each iteration". Binary search, a popular O(log n) function, works by dividing the search range in half, and then recursing until the item is found. In our buffet style catering algorithm, each additional guest only contributes half as much to unlocking a new dish, as the previous guest. (You may recognize this pattern from RPG leveling)

Theoretically, in our catering algorithm we could wait until the guests triple, which would still be logarithmic time, only the base would be 3. But working with 2 parts is more natural, and it works better with Booleans, so most of the time the base of your logarithmic algorithms will be 2. That's why if you see O(log n) you can assume it to be base 2.

*1 dish at 1 guest, 2 dishes at 2 guests, 3 dishes at 4 guests, 4 dishes at 8 guests