How do you visualize difference between O(log n) and O(n log n)?

Question

Binary search has a average case performance as O(log n) and Quick Sort with O(n log n) is O(n log n) is same as O(n) + O(log n)

Answer 1

No, O(n log n) = O(n) * O(log n)

In mathematics, when you have an expression (i.e. e=mc^2), if there is no operator, then you multiply.

Normally the way to visualize O(n log n) is "do something which takes log n computations n times."

If you had an algorithm which first iterated over a list, then did a binary search of that list (which would be N + log N) you can express that simply as O(n) because the n dwarfs the log n for large values of n

Answer 2

Imagine a database with with every person in the world. That's 6.7 billion entries. O(log n) is a lookup on an indexed column (e.g. primary key). O(n log n) is returning the entire population in sorted order on an unindexed column.

• O(log n) was finished before you finished reading the first word of that sentence.
• O(n log n) is still calculating...

Another way to imagine it:

log n is proportional to the number of digits in n.

n log n is n times greater.

Try writing the number 1000 once versus writing it one thousand times. The first takes O(log n) time, the second takes O(n log n) time.

Now try that again with 6700000000. Writing it once is still trivial. Now try writing it 6.7 billion times. Even if you could write it once per second you'd be dead before you finished.

Answer 3

You could visualize it in a plot, see here for example:

Answer 4

A (log n) plot increases, but is concave downward, which means:

• It increases when n gets larger
• It's rate of increasing decreases when n gets larger

A (n log n) plot increases, and is (slightly) concave upward, which means:

• It increases when n gets larger
• It's rate of increasing (slightly) increases when n gets larger

Answer 5

Depends on whether you tend to visualize n as having a concrete value.

If you tend to visualize n as having a concrete value, and the units of f(n) are time or instructions, then O(log n) is n times faster than O(n log n) for a given task of size n. For memory or space units, then O(log n) is n times smaller for a given task of size n. In this case, you are focusing on the codomain of f(n) for some known n. You are visualizing answers to questions about how long something will take or how much memory will this operation consume.

If you tend to visualize n as a parameter having any value, then O(log n) is n times more scalable. O(log n) can complete n times as many tasks of size n. In this case, you are focused on the domain of f(n). You are visualizing answers to questions about how big n can get, or how many instances of f(n) you can run in parallel.

Neither perspective is better than the other. The former can be use to compare approaches to solving a specific problem. The latter can be used to compare the practical limitations of the given approaches.