Will a O(n) algorithm generally always win in a time-race over a O(n3) algorithm?
femtorgon2
New member
- Mar 26, 2009
- 3
- 0
- 1
No. That notation is the time complexity. Effectively, it denotes a function describing how much an increasing size of n cause the time taken to grow. O
algorithms time grows linearly, O(n^3) grows exponentially. It is guaranteed that an O(n^3) will for a high enough value of n will surpass the O, but for lower values of n, the exponential algorithm's actual time may certainly be lower.
Consider this example. I have two algorithms. One completes in:
(1000n) seconds
an O algorithm
The other in:
(n^3) seconds
an O(n^3) algorithm
if n=5, the O algorithm completes in 5000 seconds, while the O(n^3) algorithms completes in only 125 seconds.
Not until we get up to n = 32 does the O algorithm become faster.
algorithms time grows linearly, O(n^3) grows exponentially. It is guaranteed that an O(n^3) will for a high enough value of n will surpass the O, but for lower values of n, the exponential algorithm's actual time may certainly be lower.Consider this example. I have two algorithms. One completes in:
(1000n) seconds
an O
algorithmThe other in:
(n^3) seconds
an O(n^3) algorithm
if n=5, the O
algorithm completes in 5000 seconds, while the O(n^3) algorithms completes in only 125 seconds. Not until we get up to n = 32 does the O
algorithm become faster.femtorgon2
New member
- Mar 26, 2009
- 3
- 0
- 1
No. That notation is the time complexity. Effectively, it denotes a function describing how much an increasing size of n cause the time taken to grow. O algorithms time grows linearly, O(n^3) grows exponentially. It is guaranteed that an O(n^3) will for a high enough value of n will surpass the O, but for lower values of n, the exponential algorithm's actual time may certainly be lower.
Consider this example. I have two algorithms. One completes in:
(1000n) seconds
an O algorithm
The other in:
(n^3) seconds
an O(n^3) algorithm
if n=5, the O algorithm completes in 5000 seconds, while the O(n^3) algorithms completes in only 125 seconds.
Not until we get up to n = 32 does the O algorithm become faster.
algorithms time grows linearly, O(n^3) grows exponentially. It is guaranteed that an O(n^3) will for a high enough value of n will surpass the O, but for lower values of n, the exponential algorithm's actual time may certainly be lower.Consider this example. I have two algorithms. One completes in:
(1000n) seconds
an O
algorithmThe other in:
(n^3) seconds
an O(n^3) algorithm
if n=5, the O
algorithm completes in 5000 seconds, while the O(n^3) algorithms completes in only 125 seconds. Not until we get up to n = 32 does the O
algorithm become faster.