5 replies to this topic

[toto_7]

Hello,

I would like to ask, why this time complexity is the best choice for small values despite that it is the worst against O(1) and O(n)?
thank you

[lethalwire]

For smaller values, O(N^3) isn't always a bad choice.
Let's say your algorithm takes a list of size N and executes in 9 seconds, then this might be feasible for you.

However, if you multiply the size of your list by 3 then this time increases by factor of 9s^3 which is 729 seconds. This might NOT be feasible for you.

Sometimes O(N^3) solutions are more straightforward and easier to implement. But if you know your algorithm won't take large values of N then you might be fine.
However, if you know your algorithm might take larger values of N, you will have to see how feasible this execution time is for you.

If it is not feasible, you'll have to optimize your current algorithm to pass your time constraints.

[WingedPanther]

The key to understanding it is that there can be a multiplier on the true function.

So, for example,
100000 is O(1)
10000*x is O(n)
1000*x*x is O(n^2)
100*x*x*x is O(n^3)

When x = 1 or 2, however, the O(n^3) executes faster.

[toto_7]

I have understand how it works but the main reason that this complexity is the best for small inputs, what it is? Only because is fast?

[lethalwire]

toto_7 said:

I have understand how it works but the main reason that this complexity is the best for small inputs, what it is? Only because is fast?

define small inputs
define fast

O(N^3) algorithms don't always perform faster than O(N^2), O(N) or O(1) algorithms. So technically, your O(N^3) algorithm might NOT be faster than others. Even for "small input."

[WingedPanther]

You have to compute the actual number of cycles/memory/whatever for the input.

In my example above, plug in 2 for x:
100000 is O(1) -> 100,000 cycles
10000*x is O(n) -> 20,000 cycles
1000*x*x is O(n^2) -> 4,000 cycles
100*x*x*x is O(n^3) -> 800 cycles

Now, if you plug in 10 for each of them, they'll each be the same, and if you plug in 100, you'll see that they reflect the normal ordering. If you have a function that contains 100 statements, it is complexity O(1), because the inputs don't matter. When compared to something that has a nested for loop around 1 statement, it will be O(n^2), because of the nested loop, but that just tells you how rapidly it grows relative to the input. It doesn't tell you it takes longer to run than the other function for ALL inputs.

In general, O(n) scales better than O(n^2), but that doesn't mean that for your particular situation that it will be faster, if you only have small inputs. I know of a circumstance where a function was coded as O(n^2) complexity, and it was doing a database query to a database across the ocean. When it was changed to O(n), with a single beefy query up front, it sped up a lot, but the up front query took a while.