What does O(log n) mean exactly?

I cannot understand how to identify a function with a log time.

The most common attributes of logarithmic running-time function are that:

• the choice of the next element on which to perform some action is one of several possibilities, and
• only one will need to be chosen.

or

• the elements on which the action is performed are digits of n

This is why, for example, looking up people in a phone book is O(log n). You don't need to check every person in the phone book to find the right one; instead, you can simply divide-and-conquer by looking based on where their name is alphabetically, and in every section you only need to explore a subset of each section before you eventually find someone's phone number.

Of course, a bigger phone book will still take you a longer time, but it won't grow as quickly as the proportional increase in the additional size.

We can expand the phone book example to compare other kinds of operations and their running time. We will assume our phone book has businesses (the "Yellow Pages") which have unique names and people (the "White Pages") which may not have unique names. A phone number is assigned to at most one person or business. We will also assume that it takes constant time to flip to a specific page.

Here are the running times of some operations we might perform on the phone book, from fastest to slowest:

• O(1) (in the worst case): Given the page that a business's name is on and the business name, find the phone number.

• O(1) (in the average case): Given the page that a person's name is on and their name, find the phone number.

• O(log n): Given a person's name, find the phone number by picking a random point about halfway through the part of the book you haven't searched yet, then checking to see whether the person's name is at that point. Then repeat the process about halfway through the part of the book where the person's name lies. (This is a binary search for a person's name.)

• O(n): Find all people whose phone numbers contain the digit "5".

• O(n): Given a phone number, find the person or business with that number.

• O(n log n): There was a mix-up at the printer's office, and our phone book had all its pages inserted in a random order. Fix the ordering so that it's correct by looking at the first name on each page and then putting that page in the appropriate spot in a new, empty phone book.

For the below examples, we're now at the printer's office. Phone books are waiting to be mailed to each resident or business, and there's a sticker on each phone book identifying where it should be mailed to. Every person or business gets one phone book.

• O(n log n): We want to personalize the phone book, so we're going to find each person or business's name in their designated copy, then circle their name in the book and write a short thank-you note for their patronage.

• O(n²): A mistake occurred at the office, and every entry in each of the phone books has an extra "0" at the end of the phone number. Take some white-out and remove each zero.

• O(n · n!): We're ready to load the phonebooks onto the shipping dock. Unfortunately, the robot that was supposed to load the books has gone haywire: it's putting the books onto the truck in a random order! Even worse, it loads all the books onto the truck, then checks to see if they're in the right order, and if not, it unloads them and starts over. (This is the dreaded bogo sort.)

• O(nⁿ): You fix the robot so that it's loading things correctly. The next day, one of your co-workers plays a prank on you and wires the loading dock robot to the automated printing systems. Every time the robot goes to load an original book, the factory printer makes a duplicate run of all the phonebooks! Fortunately, the robot's bug-detection systems are sophisticated enough that the robot doesn't try printing even more copies when it encounters a duplicate book for loading, but it still has to load every original and duplicate book that's been printed.

O(log N) basically means time goes up linearly while the n goes up exponentially. So if it takes 1 second to compute 10 elements, it will take 2 seconds to compute 100 elements, 3 seconds to compute 1000 elements, and so on.

​It is O(log n) when we do divide and conquer type of algorithms e.g binary search. Another example is quick sort where each time we divide the array into two parts and each time it takes O(N) time to find a pivot element. Hence it N O(log N)

Many good answers have already been posted to this question, but I believe we really are missing an important one - namely, the illustrated answer.

What does it mean to say that the height of a complete binary tree is O(log n)?

The following drawing depicts a binary tree. Notice how each level contains double the number of nodes compared to the level above (hence binary):

Binary search is an example with complexity O(log n). Let's say that the nodes in the bottom level of the tree in figure 1 represents items in some sorted collection. Binary search is a divide-and-conquer algorithm, and the drawing shows how we will need (at most) 4 comparisons to find the record we are searching for in this 16 item dataset.

Assume we had instead a dataset with 32 elements. Continue the drawing above to find that we will now need 5 comparisons to find what we are searching for, as the tree has only grown one level deeper when we multiplied the amount of data. As a result, the complexity of the algorithm can be described as a logarithmic order.

Plotting log(n) on a plain piece of paper, will result in a graph where the rise of the curve decelerates as n increases:

If you had a function that takes:

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2^n elements.

Then it takes log₂(n) time. The Big O notation, loosely speaking, means that the relationship only needs to be true for large n, and that constant factors and smaller terms can be ignored.

The logarithm

Ok let's try and fully understand what a logarithm actually is.

Imagine we have a rope and we have tied it to a horse. If the rope is directly tied to the horse, the force the horse would need to pull away (say, from a man) is directly 1.

Now imagine the rope is looped round a pole. The horse to get away will now have to pull many times harder. The amount of times will depend on the roughness of the rope and the size of the pole, but let's assume it will multiply one's strength by 10 (when the rope makes a complete turn).

Now if the rope is looped once, the horse will need to pull 10 times harder. If the human decides to make it really difficult for the horse, he may loop the rope again round a pole, increasing it's strength by an additional 10 times. A third loop will again increase the strength by a further 10 times.

We can see that for each loop, the value increases by 10. The number of turns required to get any number is called the logarithm of the number i.e. we need 3 posts to multiple your strength by 1000 times, 6 posts to multiply your strength by 1,000,000.

3 is the logarithm of 1,000, and 6 is the logarithm of 1,000,000 (base 10).

So what does O(log n) actually mean?

In our example above, our 'growth rate' is O(log n). For every additional loop, the force our rope can handle is 10 times more:

Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n

Now the example above did use base 10, but fortunately the base of the log is insignificant when we talk about big o notation.

Now let's imagine you are trying to guess a number between 1-100.

Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  

Now it took you 7 guesses to get this right. But what is the relationship here? What is the most amount of items that you can guess from each additional guess?

Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024

Using the graph, we can see that if we use a binary search to guess a number between 1-100 it will take us at most 7 attempts. If we had 128 numbers, we could also guess the number in 7 attemps but 129 numbers will takes us at most 8 attempts (in relations to logarithms, here we would need 7 guesses for a 128 value range, 10 guesses for a 1024 value range. 7 is the logarithm of 128, 10 is the logarithm of 1024 (base 2)).

Notice that I have bolded 'at most'. Big-O notation always refers to the worse case. If you're lucky, you could guess the number in one attempt and so the best case is O(1), but that's another story.

We can see that for every guess our data set is shrinking. A good rule of thumb to identify if an algorithm has a logarithmtic time is to see if the data set shrinks by a certain order after each iteration

What about O(n log n)?

You will eventually come across a linearithmic time O(n log(n)) algorithm. The rule of thumb above applies again, but this time the logarithmic function has to run n times e.g. reducing the size of a list n times, which occurs in algorithms like a mergesort.

You can easily identify if the algorithmic time is n log n. Look for an outer loop which iterates through a list (O(n)). Then look to see if there is an inner loop. If the inner loop is cutting/reducing the data set on each iteration, that loop is (O(log n)), and so the overall algorithm is = O(n log n).

Disclaimer: The rope-logarithm example was grabbed from the excellent Mathematician's Delight book by W.Sawyer.

Logarithmic running time (O(log n)) essentially means that the running time grows in proportion to the logarithm of the input size - as an example, if 10 items takes at most some amount of time x, and 100 items takes at most, say, 2x, and 10,000 items takes at most 4x, then it's looking like an O(log n) time complexity.

You can think of O(log N) intuitively by saying the time is proportional to the number of digits in N.

If an operation performs constant time work on each digit or bit of an input, the whole operation will take time proportional to the number of digits or bits in the input, not the magnitude of the input; thus, O(log N) rather than O(N).

If an operation makes a series of constant time decisions each of which halves (reduces by a factor of 3, 4, 5..) the size of the input to be considered, the whole will take time proportional to log base 2 (base 3, base 4, base 5...) of the size N of the input, rather than being O(N).

And so on.

What's log_b(n)?

It is the number of times you can cut a log of length n repeatedly into b equal parts before reaching a section of size 1.

The best way I've always had to mentally visualize an algorithm that runs in O(log n) is as follows:

If you increase the problem size by a multiplicative amount (i.e. multiply its size by 10), the work is only increased by an additive amount.

Applying this to your binary tree question so you have a good application: if you double the number of nodes in a binary tree, the height only increases by 1 (an additive amount). If you double it again, it still only increased by 1. (Obviously I'm assuming it stays balanced and such). That way, instead of doubling your work when the problem size is multiplied, you're only doing very slightly more work. That's why O(log n) algorithms are awesome.

Divide and conquer algorithms usually have a logn component to the running time. This comes from the repeated halving of the input.

In the case of binary search, every iteration you throw away half of the input. It should be noted that in Big-O notation, log is log base 2.

Edit: As noted, the log base doesn't matter, but when deriving the Big-O performance of an algorithm, the log factor will come from halving, hence why I think of it as base 2.

O(log n) is a bit misleading, more precisely it's O(log₂ n), i.e. (logarithm with base 2).

The height of a balanced binary tree is O(log₂ n), since every node has two (note the "two" as in log₂ n) child nodes. So, a tree with n nodes has a height of log₂ n.

Another example is binary search, which has a running time of O(log₂ n) because at every step you divide the search space by 2.

O(log n) refers to a function (or algorithm, or step in an algorithm) working in an amount of time proportional to the logarithm (usually base 2 in most cases, but not always, and in any event this is insignificant by big-O notation*) of the size of the input.

The logarithmic function is the inverse of the exponential function. Put another way, if your input grows exponentially (rather than linearly, as you would normally consider it), your function grows linearly.

O(log n) running times are very common in any sort of divide-and-conquer application, because you are (ideally) cutting the work in half every time. If in each of the division or conquer steps, you are doing constant time work (or work that is not constant-time, but with time growing more slowly than O(log n)), then your entire function is O(log n). It's fairly common to have each step require linear time on the input instead; this will amount to a total time complexity of O(n log n).

The running time complexity of binary search is an example of O(log n). This is because in binary search, you are always ignoring half of your input in each later step by dividing the array in half and only focusing on one half with each step. Each step is constant-time, because in binary search you only need to compare one element with your key in order to figure out what to do next irregardless of how big the array you are considering is at any point. So you do approximately log(n)/log(2) steps.

The running time complexity of merge sort is an example of O(n log n). This is because you are dividing the array in half with each step, resulting in a total of approximately log(n)/log(2) steps. However, in each step you need to perform merge operations on all elements (whether it's one merge operation on two sublists of n/2 elements, or two merge operations on four sublists of n/4 elements, is irrelevant because it adds to having to do this for n elements in each step). Thus, the total complexity is O(n log n).

*Remember that big-O notation, by definition, constants don't matter. Also by the change of base rule for logarithms, the only difference between logarithms of different bases is a constant factor.

It simply means that the time needed for this task grows with log(n) (example : 2s for n = 10, 4s for n = 100, ...). Read the Wikipedia articles on Binary Search Algorithm and Big O Notation for more precisions.

Simply put: At each step of your algorithm you can cut the work in half. (Asymptotically equivalent to third, fourth, ...)

If you plot a logarithmic function on a graphical calculator or something similar, you'll see that it rises really slowly -- even more slowly than a linear function.

This is why algorithms with a logarithmic time complexity are highly sought after: even for really big n (let's say n = 10^8, for example), they perform more than acceptably.

Every time we write an algorithm or code we try to analyze its asymptotic complexity. It is different from its time complexity.

Asymptotic complexity is the behavior of execution time of an algorithm while the time complexity is the actual execution time. But some people use these terms interchangeably.

Because time complexity depends on various parameters viz.
1. Physical System
2. Programming Language
3. coding Style
4. And much more ......

The actual execution time is not a good measure for analysis.

Instead we take input size as the parameter because whatever the code is, the input is same. So the execution time is a function of input size.

Following is an example of Linear Time Algorithm

Linear Search
Given n input elements, to search an element in the array you need at most 'n' comparisons. In other words, no matter what programming language you use, what coding style you prefer, on what system you execute it. In the worst case scenario it requires only n comparisons.The execution time is linearly proportional to the input size.

And its not just search, whatever may be the work (increment, compare or any operation) its a function of input size.

So when you say any algorithm is O(log n) it means the execution time is log times the input size n.

As the input size increases the work done(here the execution time) increases.(Hence proportionality)

      n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work

See as the input size increased the work done is increased and it is independent of any machine. And if you try to find out the value of units of work It's actually dependent onto those above specified parameters.It will change according to the systems and all.

The complete binary example is O(ln n) because the search looks like this:

1 2 3 4 5 6 7 8 9 10 11 12

Searching for 4 yields 3 hits: 6, 3 then 4. And log2 12 = 3, which is a good apporximate to how many hits where needed.

O(logn) is one of the polynomial time complexity to measure the runtime performance of any code.

I hope you have already heard of Binary search algorithm.

Let's assume you have to find an element in the array of size N.

Basically, the code execution is like N N/2 N/4 N/8....etc

If you sum all the work done at each level you will end up with n(1+1/2+1/4....) and that is equal to O(logn)

I would like to add that the height of the tree is the length of the longest path from the root to a leaf, and that the height of a node is the length of the longest path from that node to a leaf. The path means the number of nodes we encounter while traversing the tree between two nodes. In order to achieve O(log n) time complexity, the tree should be balanced, meaning that the difference of the height between the children of any node should be less than or equal to 1. Therefore, trees do not always guarantee a time complexity O(log n), unless they are balanced. Actually in some cases, the time complexity of searching in a tree can be O(n) in the worst case scenario.

You can take a look at the balance trees such as AVL tree. This one works on balancing the tree while inserting data in order to keep a time complexity of (log n) while searching in the tree.

Big O notations For reference. this may help !

Big O--------------- Sorting-------------- Complexity

O(log N)     -Binary search      - logarithmic

O(N)         -Simple search      - Linear

O(N*log N)   -Quicksort          - loglinear 

O(2^N)       -recursive          - Exponential

O(N2)        -Selection sort     - directly proportional to the square of the input size.