• What does the time complexity O(log n) actually mean?
  • Original author: Maaz
  • The Nuggets translation Project
  • Translator: cdpath
  • Proofreader: Zaraguo (Zaraguo), Whatbeg (Qiu Hu)

It is one thing to know the complexity of an algorithm in advance; it is quite another to know the principles behind it.

Whether you have a computer science background or want to effectively solve optimization problems, you must understand time complexity if you want to use your knowledge to solve practical problems.

Let’s start with the straightforward O(1) and O(n) complexity. O(1) means a single operation to retrieve the target element (such as a dictionary or hash table), and O(n) means to search for the target by checking n elements first, but what does O(log n) mean?

You probably first heard of order log n time complexity when you were learning binary search algorithms. Binary search must have some behavior that makes it log n in time. Let’s see how binary search is implemented.

Since binary search is O(1) in the best case and O(log n) in the worst case (average case), let’s go straight to the worst-case example. We have an ordered array of 16 elements.

For a worst-case example, let’s say we’re looking for the number 13.

An ordered array of 16 elements

Choose the middle element as the center point (half the length)

13 is less than the center, so you don’t have to worry about the last half of the array

Repeat the process, looking for the middle element of the subarray each time

Each comparison with an intermediate element halves the search scope.

So in order to find the target element from the 16 elements, we need to split the array four times on average, which means,

The simplified formula

Similarly, if I have n elements,

Summary of

I’m going to plug in the numerator and denominator

Multiply both sides of this equation by 2 to the k

The final result

Now let’s look at the definition of logarithm:

The exponent of the power to which a number (base) must be multiplied to equal a given number.

In other words, it could be written this way

Logarithmic form

So log n does make sense, doesn’t it? There is nothing else to represent this behavior.

That’s it. I hope I’ve made sense to you. This is always useful (and fun) to know when working in computer science. Maybe because you know how the algorithm works, you’re the one on the team who can figure out the best solution to the problem. Who knows. Good luck!

The Nuggets Translation Project is a community that translates quality Internet technical articles from English sharing articles on nuggets. Android, iOS, React, front end, back end, product, design, etc. Keep an eye on the Nuggets Translation project for more quality translations.