64
$\begingroup$

I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$.

In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of the list. $\Theta(n)$ is where I'd walk the entire list once, and $\Theta(n^2)$ is walking the list once for each element in the list.

Is there a similarly intuitive way to grasp $\Theta(\log n)$ other than just knowing it lies somewhere between $\mathcal{O}(1)$ and $\Theta(n)$?

Improve this question
$\endgroup$
5
  • 8
    $\begingroup$ log n is for "searching": think binary search $\endgroup$
    – Suresh
    Mar 21, 2012 at 6:07
  • 2
    $\begingroup$ Using $O$ to ask this question is incorrect, as it only denotes an upper bound. For instance constant time is $\mathcal{O}(\log n)$. $\theta$ would be more appropriate. See meta question: meta.cs.stackexchange.com/questions/182/… $\endgroup$
    – Aryabhata
    Mar 22, 2012 at 21:47
  • 1
    $\begingroup$ More information on SO: what does $O(\log n)$ mean exactly?. $\endgroup$
    – Ran G.
    Apr 2, 2012 at 4:07
  • $\begingroup$ A little note: In the classical Turing Machine settings, all algorithms are $\Omega (n)$, since they need to read each symbol of the input at least once. Binary search can be done in $O(\log n)$ because we have the promise that the list is sorted, for example. $\endgroup$
    – chazisop
    Jun 19, 2012 at 13:38
  • 1
    $\begingroup$ A late contribution: by definition, the base $b$ logarithm of a number $n$ is just the number of times you multiply $b$ by itself to get $n$. $b^l = n \iff l = log_b(n)$. For example, $2^3 = 8 \iff log_2(8) = 3$. So if you have a number $n$ and you want to find out what $log_b(n) = ?$ just keep dividing it by $b$ until you reach a $1$ (assuming $n$ is a power of $b$ for simplicity). The number of divisions is equal to $log_b(n)$. Algorithms that exhibit this division behavior have running times in $O(log(n))$. $\endgroup$
    – mrk
    Aug 20, 2012 at 3:13

8 Answers 8

Reset to default
56
$\begingroup$

The $\Theta(\log n)$ complexity is usually connected with subdivision. When using lists as an example, imagine a list whose elements are sorted. You can search in this list in $\mathcal{O}(\log n)$ time - you do not actually need to look at each element because of the sorted nature of the list.

If you look at the element in the middle of the list and compare it to the element you search for, you can immediately say whether it lies in the left or right half of the array. Then you can just take this one half and repeat the procedure until you find it or reach a list with 1 item which you trivially compare.

You can see that the list effectively halves each step. That means if you get a list of length $32$, the maximum steps you need to reach one-item list is $5$. If you have a list of $128 = 2^7$ items, you need only $7$ steps, for a list of $1024 = 2^{10}$ you need only $10$ steps etc.

As you can see, the exponent $n$ in $2^n$ always shows the number of steps necessary. Logarithm is used to "extract" exactly this exponent number, for example $\log_2 2^{10} = 10$. It also generalizes to list lengths that are not powers of two long.

Improve this answer
$\endgroup$
13
  • 5
    $\begingroup$ It should be noted that this is only O(log n) if the list has constant time random access. On more typical list implementations (linked lists) this is O(n log n) $\endgroup$
    – asm
    Mar 21, 2012 at 12:53
  • 2
    $\begingroup$ Binary search does not work on lists for the lack of pointers; it is usually done on arrays. $\endgroup$
    – Raphael ♦
    Mar 21, 2012 at 13:08
  • $\begingroup$ Binary search works just fine on lists. It's just quite pointless on account of being a lot more complicated than required/usefull/practical. $\endgroup$
    – Anton
    Mar 21, 2012 at 15:18
  • $\begingroup$ @AndrewMyers Searching a linked list is more accurately $\mathcal{O}(n)$ $\endgroup$
    – phant0m
    Sep 30, 2012 at 21:37
  • 1
    $\begingroup$ @phant0m Yeah, took me a bit to figure out that it's assuming you're moving from the current position instead of traversing from the beginning every time. $\endgroup$
    – asm
    Oct 3, 2012 at 15:06
38
$\begingroup$

In terms of (balanced) trees (say, binary tree, so all $\log$'s are base 2):

  • $\Theta(1)$ is getting the root of the tree
  • $\Theta(\log n)$ is a walk from root to leaf
  • $\Theta(n)$ is traversing all nodes of the tree
  • $\Theta(n^2)$ is actions on all the subsets two nodes in the tree, e.g., the number of different paths between any two nodes.
  • $\Theta(n^k)$ - generalization of the above for any subset of $k$ nodes (for a constant $k$)
  • $\Theta(2^n)$ is actions on all the possible subsets of nodes (subsets of all the possible sizes, i.e., $k=1,2, \ldots, n$.). For instance, the number of different sub-trees of the tree.
Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ To add to this, intuition for $\Theta(log\,log\,n)$ comes from two things: 1.) The recurrence $T(n) = T(\sqrt(n)) + 1$ and 2.) Binary search on something of size $log(n)$ i.e. a binary search on the height of the tree. $\endgroup$
    – mcorley
    Mar 25, 2012 at 16:49
18
$\begingroup$

For $O(\log n)$ to be possible, you need to be able to cut down the problem size proportionally by some arbitrary amount with respect to $n$ with a constant time operation.

For example, in the case of binary search, you can cut down the problem size by a half with each comparison operation.

Now, do you have to cut down the problem size by half, actually no. An algorithm is $O(\log n)$ even if it can cut down the problem search space by 0.0001%, as long as the percentage and the operation it uses to cut down the problem size stays constant, it's a $O(\log n)$ algorithm, it won't be a fast algorithm, but it's still $O(\log n)$ with a very large constant. (Assuming we are talking about $\log n$ with a base 2 log)

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ What would it be if the 'down cutting amount' wasn't constant? $\endgroup$
    – Svish
    Mar 21, 2012 at 15:04
  • $\begingroup$ @Svish If you can cut the problem down at a positive rate, it would still be a $O(\log n)$ algorithm, although it probably would no longer be a tight bound. Negative rate is hard to say. The assumption was made to make the answer rather simple in this case, since this question has its own merit, you are more than welcome to ask this as a question on its own. $\endgroup$
    – Ken Li
    Mar 21, 2012 at 21:42
  • $\begingroup$ Yeah, I was meaning that the problem search space always decreased, but not necessarily at a constant rate. Was just thinking of your "as long as the percentage and the operation it uses to cut down the problem size stays constant, it's a O(log n) algorithm"; if it had a different name if the percentage there wasn't constant. $\endgroup$
    – Svish
    Mar 21, 2012 at 22:15
9
$\begingroup$

Think about algorithm to convert decimal number $n$ to binary

while n != 0:
   print n%2, 
   n = n/2

This while loop runs $\log(n)$ times.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Certainly this program loops $\log n$ times, but generally when we talk about $O(f(s))$ complexity, $s$ is the size of your input. Here the size of your input is already $s=\log n$, so I would say this program is only linear (in $O(s)$) $\endgroup$
    – jmad
    Mar 21, 2012 at 14:02
  • $\begingroup$ @jmad Right. But this example does give you intuition into log(n). $\endgroup$
    – Pratik Deoghare
    Mar 21, 2012 at 14:05
  • $\begingroup$ @jmad I could have used algorithm to generate random numbers too but I wanted it as simple as possible. $\endgroup$
    – Pratik Deoghare
    Mar 21, 2012 at 14:10
  • $\begingroup$ Is it just me or does this algorithm not work for values over 100? $\endgroup$
    – Ashley
    Jul 11, 2020 at 6:13
9
$\begingroup$

Yes, $\log(n)$ is between $1$ and $n$, but it is closer to $1$ than $n$. What is $\log(n)$? The log function is the inverse function of exponentation. Let me start with exponentation and you should get a better idea of what logarithm is.

Consider two numbers, $100$ and $2^{100}$. $2^{100}$ is $2$ multiplied with itself $100$ times. You can with some effort count $100$ numbers, but can you count $2^{100}$? I bet you can't. Why? $2^{100}$ is such a big number that it is greater than the number of all atoms in the universe. Reflect on that for a moment. It is such a huge number, that it allows you to give each atom a name (number). And the number of atoms in your finger nail is probably in the order of billions. $2^{100}$ ought to be enough for anyone (pun intended :)).

Now, between the two numbers, $100$ and $2^{100}$, $100$ is the logarithm of $2^{100}$ (in base $2$). $100$ is comparatively such a small number than $2^{100}$. Anybody ought to have $100$ different items in their home. But, $2^{100}$ is good enough for the universe. Think home vs universe when thinking of $\log(n)$ and $n$.

Where do exponentation and logarithms come from? Why are they of so much interest in computer science? You may not notice, but exponentation is everywhere. Did you pay interest on credit card? You just paid a universe for your home (Not so bad, but the curve fits). I like to think that exponentation comes from product rule, but others are welcome to give more examples. What's product rule, you may ask; And I shall answer.

Say you have two cities $A$ and $B$, and there are two ways to go between them. What is the number of paths between them? Two. That is trivial. Now say, there is another city $C$, and you can go from $B$ to $C$ in three ways. How many paths are there between $A$ and $C$ now? Six, right? How did you get that? Did you count them? Or did you multiply them? Either way, it is easy to see that both ways give a similar result. Now if you add a city $D$ which can be reached from $C$ in four ways, how many ways are there between $A$ and $D$? Count if you don't trust me, but it is equal to $2\cdot 3\cdot 4$ which is $24$. Now, if there are ten cities and there are two paths from one city to the next, and they are arranged like they are on a straight line. How many paths are there from start to end? Multiply them if you don't trust me, but I will tell you there are $2^{10}$, which is $1024$. See that $2^{10}$ is exponential result of $10$, and $10$ is the logarithm of $2^{10}$. $10$ is a small number compared to $1024$.

The logarithm function $\log_2(n)$ is to $n$ what $n$ is to $2^n$ (note that $2$ is the logarithm's base). If you multipy $\log_b(n)$ with itself $b$ times (note that $b$ is the logarithm's base) you get $n$. $\log(n)$ is so tiny, so small compared with $n$, that it is size of your home where $n$ is size of the universe.

On a practical note, $\log(n)$ functions perform very similar to constant functions. They do grow with $n$, but they grow very slowly. If you optimized a program to run in logarithmic time which was taking a day before, you will probably run it in the order of minutes. Check for yourself with problems on Project Euler.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ While nicely written, this answer contains hardly any information besides "$\log(n)$ is really small". $\endgroup$
    – Raphael ♦
    Mar 21, 2012 at 13:05
  • 3
    $\begingroup$ I was trying to give an intuition for how small it is. $\endgroup$
    – Ravi
    Mar 21, 2012 at 21:36
6
$\begingroup$

To continue your theme, $O(\log n)$ is like repeatedly guessing where $x$ lies in the list and being told "higher" or "lower" (in terms of index).

It's still based on the size of the list, but you only need to visit a fraction of the elements.

Improve this answer
$\endgroup$
5
$\begingroup$

If we have a divide and conquer algorithm, and we make only one recursive call for a subproblem, and it is the second case in Master theorem, i.e. the time complexity of the non-recursive part is $\Theta(\lg^k n)$, then the complexity of the algorithm will be $\Theta(\lg^{k+1} n)$.

In other words, when we have a divide and conquer algorithm with one recursive call to itself on a problem with size a constant factor of the current problem, and the time in the non-recursive part is $\Theta(1)$ (constant), then the running time of the algorithm is going to be $\lg n$.

The binary search algorithm is the classical example.

Improve this answer
$\endgroup$
2
$\begingroup$

The intuition is how many times you can halve a number, say n, before it is reduced to 1 is O(lg n).

For visualizing, try drawing it as a binary tree and count the number of levels by solving this geometric progression.

2^0+2^1+...+2^h = n
Improve this answer
$\endgroup$
1
  • $\begingroup$ Welcome to the site! What you say is, of course, true but I don't see what it adds to the existing answers. Several of the answers already say that the logarithm is the number of times you can divide by two before hitting 1, and Ran's answer already says that $\log n$ is the height of a binary tree with $n$ leaves. $\endgroup$
    – David Richerby
    Dec 28, 2016 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.