What does O(log n) mean, exactly?

http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly/2307314#2307314

by martindale • 13 years ago

145 85 13 years ago

zura• 13 years ago

First associations for me - sympathy, elegance (without even looking at the code), thought about that the data should be prepared (most likely sorted), thought about that this might be one particular operation and [data structure] might imply that other operations could have different O's.

Well, and finally I'll actually look at it (click on the link).

loser777• 13 years ago

Why doesn't anyone actually mention what Big O (of anything) actually means? Instead of jumping directly to a CS-related example, shouldn't the definition be made clear first?

http://en.wikipedia.org/wiki/Big_O_notation

eieio5• 13 years ago

Nobody explains Big O because the OP demonstrates that he understands the idea of Big O by giving the complexity of a piece of code and explaining how the complexity would change if the code changes.

OP is confused with the idea of O(log n), not of Big O in general.

hayksaakian• 13 years ago

The phone book example was genius. I wish they would have taught that in school.

BHSPitMonkey• 13 years ago

They usually do, if "school" is a computer science (or surely even just mathematics) program.

shoo• 13 years ago

it describes those infinite sequences of real numbers that grow no faster than logarithmically, ignoring constant factors and anything the sequence might do for a finite number of terms at the start.

assume f : N -> R. by "f in O(log n)" we mean there exist constants c >= 0 in R, m in N, such that for all n in N, if n >= m then f(n) <= c log(n)

eieio5• 13 years ago

The answer provides an excellent definition and some great examples, but I actually prefer the second answer. I think that when it comes to time complexities, developing an intuitive mapping of solutions to time complexities is important.

Developing a feel for how log(n) tends to emerge in common programming techniques is much more practical than specifically checking your code for situations where "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."

That being said, I'm not the OP and it's very possible that the phone book examples are more helpful in developing that understanding for other people.

sirclueless• 13 years ago

I think the first answer's intuition is actually better. It's stated a little opaquely, so maybe it's not actually useful as a teaching tool until you already understand why binary-search type algorithms that rule out a significant fraction of the input at each step are O(log n).

Basically, phrasing big-O as a property of the algorithm rather than the tree-structure of the solution space is more helpful in practice. I think it's quite common to have some problem in front of you and say "OK, so I can see immediately there's a naive solution thats linear, is there a smarter way?" And the answer nearly always comes (for me at least) when I try to answer the question, "Can I find some way to make smarter decisions at each step?" If the answer is "yes" or "maybe", you might be able to get to O(log n), but quite often the answer is "no" because you're streaming random data or something, or you have some logical reason why you have to look at every single input object, and you can immediately rule out better solutions and just get to work on the linear one.

That insight rarely comes to me when I ask "Is there any way to think of the input as a balanced binary search tree?" If there actually is such a tree structure, you're bound to find it anyways by asking "What smart decision am I making at each level?"

eieio5• 13 years ago

I agree that I rarely find myself asking whether I can represent input as a binary search tree, I just find the binary search tree image a very effective method of demonstrating how logarithms play into this at all. It's an easy example of log n complexity.

That being said I'm not sure how much my speculation is worth here. I'm very comfortable with the idea of log n based complexity and don't remember how it was taught to me in the first place. Given that OP accepted the answer and that it was significantly more votes, it seems that it's helpful for more people.

orionblastar7• 13 years ago

It is designed to estimate the amount of time it takes to run an algorithm using a data structure like a binary tree instead of a different one like a linked list O(n)instead for linked lists. I am trying to learn it myself, so bare with me if I make any mistakes.

They throw words like polynomial and I've asked people with comp sci degrees to define what they are. I get back replies like "We learned it as a polynomial and never got a definition of it." OK look, here is what it means and some people with a comp sci PHD cannot even tell me, poly means many, right, and nomial like numbers or formulas or rather in computer science and algorythm. You have to study how algorithms work, I asked this on Hacker News and many tried to bury the story because most couldn't even answer that, and thanks to those who did. I am glad to see someone else bring it up and hope it sheds more light on it.

Consider this, that you really cannot get a good estimate of how long any algorithm can run because you got other factors in play. You got multicore CPUs now, and some of the work is offloaded to GPUs as well (like Bitcoin mining programs using GPUs, well now algorithms can use GPUs for some of the processing), plus you got caches on processors you didn't have in 1971, not only that but the law of thermodynamics applies to computers and electronics and many people forget that, so if your CPU is over heating it could slow down if you have a variable fan it could cool the CPU down and it runs faster for a bit and then heats up and slows down a bit, most operating systems are multitasking so the program that runs the algorithm might take longer if the Apache HTTPD server is in use with heavy traffic on the server the algorythm runs on, not only that but Anonymous might have sent a DDoS attack to your server the algorithm is running on. I hope those with a PHD in computer science figure those as factors when they explore this issue.

tincholio• 13 years ago

>It is designed to estimate the amount of time it takes to run an algorithm using a data structure like a linked list instead of a different one like a binary tree.

Wat?? Excuse me, but it seems you have no idea what you're talking about.

>Consider this, that you really cannot get a good estimate of how long any algorithm can run because you got other factors in play

That has absolutely nothing to do with the complexity of the algorithm. Also, it _can_ be estimated, too.

I wonder if you're trolling or just clueless

claudius3• 13 years ago

> I wonder if you're trolling or just clueless

Given the curious interpretation of ‘polynomial’ by means of an only somewhat correct translation, I’d tend to the latter.

orionblastar7• 13 years ago

Well I am trying to understand it better. Instead of explaining it to me better, I get downvoted instead.

Please explain it further and tell me how you can estimate the time when a DDoS attack is being done on the system, or the CPU is overheating, I'd really like to know how you estimate that. Apparently I'm clueless and in need of many clues.

glurgh• 13 years ago

The entire first few chapters of CLR/The White book are dedicated to explaining this in great, patient detail.

http://en.wikipedia.org/wiki/Introduction_to_Algorithms

Just pick it up.

dschiptsov• 13 years ago

Order of growth. A shape of a function. Execution time (or memory usage) of a procedure as a function of the size of its input.

anonymouz4• 13 years ago

The example in the question seems to demonstrate a common misunderstanding with regards to Big O notation. It measures the time complexity of an algorithm in terms of its input size. But the n in the OP's example is not the input size, it is the input value.

In the actual implementation, the input size is of course constant (being an int), but if you look at the intended algorithm it is (I have renamed the variable into b on purpose, to avoid confusion with the n usually used in the Big O notation) we have something like:

* Take a number b.

* Loop from 0 to b-1 and print the number of the current iteration.

As far as this algorithm goes, the input size here is not b, but of order log(b) (number of digits to represent b), while the algorithm's runtime is proportional to b. That means this algorithm has exponential runtime.

hermannj314• 13 years ago

I'm confused by this.

His function f(x) is of linear time-complexity (with respect to the value of x). Assume it takes time c1 to print a number, this I will create a function g(x) = c1*x + k, where k is a constant representing the overhead. Then f(x) < g(x) and g(x) element of the set O(x).

I am not sure how that makes his function run in exponential time. Am I misunderstanding something?

eieio5• 13 years ago

The function runs in linear time relative to the value of x. However, time complexity refers to the size of the input, not the value. For example, binary search's O(log n) time complexity refers to the number of elements n in a list(n varies with the list's size). x + 1 will always increase the value of x, but not necessarily the size. The size of x is the number of digits in x. f(x) runs once if x=1, ten times if x=10, one hundred times if x=100, etc. So each time x's size increases by 1, f's runtime increases by a factor of 10.

It's a very literal definition of time complexity and it's counterintuitive, but ultimately it does make sense.

jmmcd• 13 years ago

Surely the n in the OP's example is the size of the input. The input is the phone book (or a given page in one case, etc) and n is the number of entries.

shawnz2• 13 years ago

OP's example accepts a parameter, and that parameter is the input size, not any of the input values. In fact, in the example, there are no input values, the function is just doing busy work -- although, I suppose it's also possible to say that i (0,1,2,3,...,n) are the values, since that's what he's printing. However, as you said, the individual input values are irrelevant to the complexity.

Consider this slightly modified function:

    f(string[] phonebook, int phonebookSize) {
      int i;
      for (i = 0; i < phonebookSize; ++i)
        printf(phonebook[i]);
    }

Here it's clear that phonebookSize (n) is the input size, not an input value -- however the function is essentially the same otherwise.

EDIT: Sorry, I understand now. You are saying that the way he's defined his function is what determines the input size. Since it accepts one integer, the complexity could be described as O(2^n) (where n is the size of the integer in bits, or digits, or whatever). I had made the assumption that my updated function is what OP's intention was.

orionblastar7• 13 years ago

I'm confused, wouldn't this be more of an O(n) instead of an O(log n) issue? If not, then what is the difference? No pointers being used, not even a data structure, just an array of strings. I expected at least a linked list data structure for a phone book. Like sorted in alphabetic order or something.

jules• 13 years ago

The value n often stands for the input size measured in bits, but not always. As long as you make it clear what n means, there is nothing wrong with using O-notation for that n. O-notation is just a way to denote a set of functions. This notation is also commonly used in mathematics and physics, where it doesn't even have anything to do with algorithms.

anonymouz4• 13 years ago

Of course, but the OP is not asking about big-O-notation in mathematics in general. He is specifically asking about what it means when applied to time complexity of algorithms.

lkozma4• 13 years ago

Your first paragraph is also a slight misunderstanding of big O notation. In fact, the notation allows to make general comparisons between the growth rates of arbitrary functions, not necessarily referring to time complexities of algorithms (although that is a frequent use of big-O notation). For example, sometimes you use big O to express the amount of space an algorithm uses, sometimes you just count some objects with a certain property, etc.

When it comes to time complexity, one always has to clarify what is the computational model assumed. What are the allowed operations? What are we counting? Are we counting the number of comparisons between arbitrary (comparable) elements? Are we counting operations on bits? Are we counting arithmetic operations on numbers that fit in a register of some idealized computer? Of course if the model is not agreed upon, the answers can differ, as in your example.

Once the model is clear, and you want to express the running time of an algorithm, the result can in fact depend on both input size and input value (although this distinction makes more sense in certain models than in others). An example is the Ford-Fulkerson algorithm for max flow, whose running time (in the RAM model) depends both on the size of the network and the value of the max flow.

anonymouz4• 13 years ago

> In fact, the notation allows to make general comparisons between the growth rates of arbitrary functions, not necessarily referring to time complexities of algorithms (although that is a frequent use of big-O notation).

True, I was simplifying by restricting to the context the OP was asking about (time complexity of an algorithm).

vitobcn• 13 years ago

In my opinion the misunderstanding arises due to the lack of understanding of what log n means, and not so much O notation.

Intuitively, logarithms are much easier to understand in the context of exponentials. For example, if there is "something" (be it a function, space, money, etc.) which starts at value "c" and doubles with each iteration: c, 2c, 4c, 8c,..., that is what we call exponential growth and iteration n would be represented by the following notation: c * 2^n.

Where does the logarithm come in? It is defined in the following way:

   if a^b = c, then log_a c = b   (note: read as log of c in base a equals to b)

so an exponential relationship can always be written in terms of logarithms.

Now, if the answer that we are looking for is not the actual value, but how many iterations did it take to get there ("b" above), that is the direct result of applying the logarithm to the function.

How does it all apply to functions execution time and Big O notation? Well, if we have a space N that we are searching over via a function F, and this function does so iteratively by dividing search space N into 2 at each iteration and discarding the wrong half, we will have the following sequence representing the space to search over at each iteration: N, N/2, N/4, ..., N * (1/2)^n.

If the question is, how long will it take this function to run? The answer is that starting at space N, the function will run until it has narrowed down the space to 1, so the search is over and it found (or not) what it was looking for. So the question is really, how many iterations will the function need to do? And as explained before this is exactly the definition of logarithm.

Therefore: ('~' defined as 'proportional to')

   time to run ~ space to search ~ # of iterations ~ log_2 (N*(1/2)^n) = constant + log (n)

In general, intuitively (not always true though) if there is a function that at each iteration is dividing the size of the work to be done by a constant factor (2,3,4,...) the run time, that is the number of iterations, will be O(log n).

dkersten2• 13 years ago

I've always read O(n) as "The worst-case (time|space) complexity in respect to n" where n is typically the input size, but could be any defined value (in this case, the value of b).

wavesounds2• 13 years ago

Did anyone make sure this guy knows that log in Computer Science is base 2? We need to remember that most places simply writing 'log' is assumed to be base 10.

Log base 2 is just how many times we can you recursively split something in half, which is not that complicated of a concept. However, his log example is base 10 and if he was trying to figure out these things as base 10 it would be super confusing and not make any sense.

geoffschmidt• 13 years ago

Well, it's like this -- log_2 and log_10 (and natural log) differ only by a constant multiplicative factor, so they're all the same asymptotically, and it doesn't matter which one you use inside the O(). Pretty neat right?

eieio5• 13 years ago

Yes, you can convert log base x to log base y. However, the point is that if OP is assuming that we're using log base 10, developing an intuitive understanding of why a binary search is O(log n) is significantly harder than if OP knows that we're referring to log base 2.

valleyer• 13 years ago

This is correct, but in case it makes more sense this way (it does to me):

log (base X) Y === log (base e) Y / log (base e) X

So the difference between log (base 2) and log (base 10) is just the difference between being divided by log (base e) 2 or log (base e) 10. Since those are both constant factors, big-O notation doesn’t care.

wavesounds2• 13 years ago

Yeah totally for the purposes of big O theory its super neat. But before you can do big O you need to be able to actually calculate the number of steps a function takes to complete. If your a student trying to figure this out for the first time and you want to divide and conquer a list of 8 elements you do 3 operations, thus you get log_2 8 = 3 or log_2 (n) = # of operations. This is then generalized in big O notation but I think trying to do big O before being able to calculate steps for an example function is putting the cart before horse.

marblar• 13 years ago

For what it's worth, when I started studying this stuff I assumed log(n) meant log_e(n). That didn't help much either.

lkozma4• 13 years ago

I find both the questions and answers confusing, I think this is a case when a little more "formal" understanding would help before jumping into "intuition" and big picture explanations.

If the question is really what O(log n) means, then the OP should first try to understand the definitions of Big-Oh notation, asymptotic growth rate, etc. At this stage it is premature to talk about running times and algorithms, these are simply statements about functions. Maybe the OP is already past this stage, or at least has a rough understanding of these concepts.

If the question is where does O(log n) arise in practice, then one can explain binary search, binary trees, the representation of a number in a certain base, harmonic series, etc.

Joeboy6• 13 years ago

I sometimes wonder, what sort of people actually need to know about Big-O notation? In about 15 years of working in IT I don't recall anybody ever using it in a work context. Generally something like "this strategy will become very slow when we have a lot of users" seems adequate. Admittedly I'm only a humble web developer. Do you regularly talk in Big-O at work? What is your job?

Edit: Despite being only a humble web developer I understand that fast algorithms are better than slow ones. I'm wondering how Big O notation is used in the real world.

gurkendoktor• 13 years ago

But what do you do once something becomes very slow? Creating a database index, for example, is a beautiful example of O(log n) :)

Joeboy6• 13 years ago

But in that case, knowing Big-O notation is a retrospective explanation of something any quarter-decent developer knows already. You don't need to know Big-O in order to know how/when to create a database index.

greenyoda3• 13 years ago

Wouldn't inserting a single record in the index be O(log n) (if n is the number of records in the index), and creating the entire index be O(n log n)?

marvin• 13 years ago

If you're working with a dumb API/library (i.e. Sharepoint) where the correct default search algorithms aren't very easily accessible, it's easy to fall into the trap of using linear-time search instead of a hashed or binary search strategy, for instance. Things will look fine until your system has been used for a while, then things will gradually slow down to a crawl.

So yes, I consider knowledge of algorithms and run-time analysis an essential software development skill (I experienced this after only 6 months on the job, so obviously our experiences differ. Consulting SharePoint developer for small businesses).

benhoyt• 13 years ago

Yes, regularly. I'm a backend web developer who works on a fairly large-scale website, and program mostly in Python. It's pretty important to know that code like this (which we have in our photo search code):

   for image in images:
       if image.hotel_id in hotel_ids:
           ...

will be O(N) if hotel_ids is a set or dict (with O(1) lookup), but O(N²) if hotel_ids is a list (with O(N) lookup). We're not talking about micro-optimizations here -- when N is of moderate size, it can mean the differences in render time between 30 milliseconds and 3 seconds.

When developers don't have a feel for this, it really slows them down -- both figuratively and literally.

FYI, I wrote a blog entry about how our photo search engine works here: http://tech.oyster.com/how-our-photo-search-engine-really-wo...

Joeboy6• 13 years ago

> When developers don't have a feel for this, it really slows them down -- both figuratively and literally.

Of course, I'm just not clear how Big-O helps with that. To me, the required insights seem to be:

* Things are slower when the computer has to do more work

* A feel for what strategies result in the computer doing more work

I can't think of many cases when saying "This algorithm is O(N^2)" is significantly more useful than saying "This algorithm is going to be really slow".

textminer• 13 years ago

I work in machine learning. I regularly get jazzed when I figured out a linear solution to a problem (e.g., using a min heap to grab top k elements from a similarity computation in a recommendation system instead of first sorting), and will remark on such to anyone I'm working with. In more mundane settings, I'll also regularly use, say, hash tables to store data for convenient constant time lookup instead of naively scanning through a list each time I need to find an index.

I think I can safely say that asymptotic time and space concerns of a problem firmly guide much of my choices in data structure and algorithm use. Though this is maybe followed closely by aesthetic pleasure, novelty of trying something new and neat, or clarity in the functional organization/readability/maintainability of the code.

0x02• 13 years ago

Even a simple PHP script that needs to work with a large data set can quickly run into problems if you don't pay attention to algorithm complexity.

Consider this simple script that first creates a dataset of strings "x0", "x2", "x4", "x6" etc. (500000 entries)

The task is to count from 0 to a 1000 to see whether the string "x"+NUMBER is present. Using a linear search with array_search() is super slow, but if you switch the storage from array values to array keys, and use a hash lookup via array_key_exists(), suddenly it flies:

% time php -dmemory_limit=512M -r '$entries = array(); for($i=0;$i<1000000;$i+=2){ $entries[] = "x".$i; }; $hits = 0; for ($i=0;$i<1000;$i++) { if(array_search("x".$i,$entries)!==false) $hits++; } var_dump($hits);' int(500) php -dmemory_limit=512M -r 11.25s user 0.09s system 99% cpu 11.362 total

So, 11.362 seconds for a linear algorithm.

% time php -dmemory_limit=512M -r '$entries = array(); for($i=0;$i<1000000;$i+=2){ $entries["x".$i]=true; }; $hits = 0; for ($i=0;$i<1000;$i++) { if(array_key_exists("x".$i,$entries)) $hits++; } var_dump($hits);' int(500) php -dmemory_limit=512M -r 0.35s user 0.06s system 99% cpu 0.419 total

And 0.419 seconds for the hash one.

If you increase the workload to counting from 0 to 10000, it gets even worse in the linear case, while the hash key lookup finishes at about the same time as earlier!

% time php -dmemory_limit=512M -r '$entries = array(); for($i=0;$i<1000000;$i+=2){ $entries[] = "x".$i; }; $hits = 0; for ($i=0;$i<10000;$i++) { if(array_search("x".$i,$entries)!==false) $hits++; } var_dump($hits);' int(5000) php -dmemory_limit=512M -r 115.96s user 0.29s system 99% cpu 1:56.52 total

So, 1 minute 56.52 seconds for a linear algorithm.

% time php -dmemory_limit=512M -r '$entries = array(); for($i=0;$i<1000000;$i+=2){ $entries["x".$i]=true; }; $hits = 0; for ($i=0;$i<10000;$i++) { if(array_key_exists("x".$i,$entries)) $hits++; } var_dump($hits);' int(5000) php -dmemory_limit=512M -r 0.37s user 0.06s system 99% cpu 0.440 total

And 0.440 seconds for the hash one.

mh-2• 13 years ago

keep in mind that since PHP must preallocate the array() to an arbitrary 'sane' size, it has to 'resize' (create a new one, copy it over, point reference, destroy old one) a large number of times here.

therefore, most of the time spent here will be malloc'ing (mmap, memcpy). the rest of it will be on executing the php interpreter, compiling the script, and cleanup.

the hash search and comparisons are so much faster than those operations (in PHP, especially), this isn't really a valid way to measure your thesis

Udo2• 13 years ago

I would argue that having a basic Big-O intuition is important for every developer. Regardless of the work you're doing, you want to write efficient code. And you want to know how something scales.

I'm also mainly a web developer. In my head, I'm thinking about Big-O a lot - not that I'd go and formally examine every bit of code, but keeping O behavior in mind leads to certain almost subconscious decisions that are going to be good for your software.

Being Big-O-aware makes sense especially in web development where latency minimization and stable scaling behavior are important. Keeping Big O in mind influences a lot of choices, from using certain language constructs to the way your database tables are modeled.

Thinking about Big O is part of being aware what your code actually does.

Joeboy6• 13 years ago

> Thinking about Big O is part of being aware what your code actually does.

I don't get this at all. Surely Big-O is an abstract way of describing a property of your code to somebody who doesn't want to read it. If Big-O gives you a better understanding of what your code does than writing it did, that suggests you wrote it by applying some kind of genetic algorithm and you should probably go back and look at it again until you understand it.

dkersten2• 13 years ago

I worry about Big-O almost every day. I run an analytics startup and scaling to huge datasets is important. Sure, I could throw hardware at the problem, but even that has its problems and bottlenecks and would also inflate cost. Instead, I carefully handpick the algorithms used (where possible) to have reasonable time/space complexities for the tasks I want to perform. Not everything needs to be carefully tuned, of course, but for the bits that do, Big-O is a useful tool.

Before this, I've used Big-O when writing some hobby game engine code to make sure that my algorithms scaled nicely as number of game objects increased.

I've also used Big-O to compare algorithms in back-end web development. Usually, I didn't care, but there were a few cases where it mattered (one specific one I remember was sending out notification emails based on a complex criteria and the operations I was measuring with O(n) was number of database queries).

lkozma4• 13 years ago

Big-O is just a formal notation for comparing growth rates of functions. You are right of course, that often one might get away without the precise formalism and rely only on a gut feeling - but there are limitations on how many things we can compare mentally.

A bit tongue in cheek one could make the following analogous statement: does anyone use greater-than or less-than or equals signs at work, as in something being "> 5" or "< 10"? In my experience "this quantity is much larger than that other quantity" or "these two quantities are roughly the same" is perfectly fine.

mseebach2• 13 years ago

It took forever for the coin to drop for me on log n, and it seems it hasn't dropped for the accepted SO answer either.

log n is the height of a tree when the log base and the branching factor of the tree is the same.

Hash lookups are log n, because the hash table implementation is typically a tree.

greenyoda3• 13 years ago

A binary search tree is O(log n), but that's not what's typically referred to as "hashing".

Hash lookups can be close to O(1) (constant time) if you use a hash function that calculates a close-to-unique index into a table based on the key's value (provided the table isn't too full, so there are few collisions). This kind of data structure is typically used for looking up identifiers (variable and function names) in a compiler.

More information here: https://en.wikipedia.org/wiki/Hash_table

avaku• 13 years ago

Maybe after this discussion PG will write an article that going to the uni is not such a bad idea after all :)

andrewparker• 13 years ago

The use of a phonebook analogy is clever, but I think the answerer should modify his answer to cover the O() running time of a trie data structure. A phonebook is essentially a trie. He talks about the "divide and conquor" approach to navigating a phonebook, but that's not how a computer would store the names. The way a computer navigates a phonebook would be interested in read about.

yuliyp• 13 years ago

A phonebook as trie would only apply if you had tabs for each letter all the way down. It's a vector of pages.

jcampbell1• 13 years ago

Why is O(N * N!) not written as O(N!)? It seems that N * N! < (N+1)! and we don't care about constant factors.

archgoon• 13 years ago

N is not a constant factor.

SamReidHughes• 13 years ago

O(N!) is not the same thing as O((N+1)!).

O(f(N)) = O(f(N+1)) is true for exponential functions and less quickly growing functions but not for things past that. (And it's not true for sufficiently quickly decreasing functions, either, in the other direction, e.g. where f(N) = 1/N!)

jgross206• 13 years ago

Not sure of the universality of this, but my intuitive way of understanding O(log n) is as follows:

An algorithm is O(log n) if you can reduce the solution space (the set of all possible solutions) by a fraction (e.g. divide it in half or divide it into tenths) using a constant number of operations.

For example, binary search is O(log n) because you can cut the solution space in half (regardless of how big it is) by using a constant number of operations.

jahitr• 13 years ago

An important fact to take in account about Big-O is that it represent the upper bound of the time or space complexity.

just2n• 13 years ago

I found CLRS's explanation of divide and conquer gives a very intuitive understanding of what a logarithmic time algorithm is doing and why it runs in logarithmic time.

A little bit of nitpicking on the accepted answer: the list seems to imply that these are "the" possible runtimes an algorithm may exhibit. But there are many cases where algorithms run in times that lie between these. Perhaps related are log-star and O(log log N) algorithms. These are even more interesting to me than logarithmic ones.

What does O(log n) mean, exactly?

Related Stories