Log n? What the heck is that? Honestly I hadn't touched logarithms since high school, and it took me quite a while to get my head around this particular time complexity, especially since how we use them to describe time complexity is not 100% the same as how they are discussed in your typical math class. I'm hoping that writing this out will help solidify the concept in my brain.
First, I'll discuss what logarithms are in math. According to the Merriam-Webster dictionary, a logarithm is "the exponent that indicates the power to which a base number is raised to produce a given number." Those words are honestly kind of confusing gibberish, so let's try to break it down.
The way I look at it, a logarithm is the opposite of an exponent. An exponent tells you how many times to multiply a base number to achieve a specific product. For example. In 103, '3' is the exponent, and you solve to get 103 = 1000.
Logarithms go the other direction. You start with a base and a product, and ask what the exponent must be. Using the numbers I just used, 10x = 1000. What should 'x' be? You would write the logarithm like so: log10(1000) = 3. Thus 3 is the number that 10 needs to be raised to to get 1000.
Mathematically, logarithms can be applied to any base. In programming, however, the base is typically assumed to be 2. This is in keeping with the binary nature of computers, of course. So when you see O(log n), the logarithm is really log2n.
The best example of an algorithm with an O(log n) is a binary search. This post breaks down what's going on there pretty clearly, but the basics is that you are cutting the data in half repeatedly to look at smaller and smaller chunks. Therefore in order to calculate the worst case run time, in which the very last element is the one you wanted, you need to know how many times you need to divide the data set in order to get down to one element.
Thinking of that in reverse, how many times do you need to multiply by 2 in order to get n? That's log2n, baby!
For visual simplicity we write that just as log n, and there we have O(log n).
So there you have it. This is beginning to settle in my brain more - I'm always so satisfied when I know why something is done the way it is. On to the next challenge!
(Completely unrelated, but as I wrote this and wrote 'algorithm' and 'logarithm' over an dover, I realized they are anagrams for each other? What does it all mean... *Insert Illuminati or X Files or something here.)
Top comments (0)