Is O(5n) = 5*O(n) ? From what I understand , O(5n) == O(n). Thus they are not equal? Please correct me if I am wrong.
6 Answers
You only care the asymptotic behavior of the function and if f(x)/g(x) converges to a constant the two functions are defined to belong to the same big-O class. So as 5*n / n is always 5. So O(n) = O(5*n).
As for your question: O(f(x)) is defined as the set of functions having the same asymptotic behavior as f(x) and thus 5*O(N) is not defined. There is no such thing.
answered Feb 27, 2013 at 16:20
Ivaylo Strandjev
71.4k18 gold badges130 silver badges183 bronze badges
12 Comments
h4ck3d
But my question is , Is O(5n) = 5*O(n) ?
amit
It does not addresses the question (which is not well defined, but still does not address it). The question was NOT if O(5n) == O(n), but for 5*O(n).
chtenb
O(n) can be seen as a the set of linear algorithm running times. So 5*O(n) is not defined, and thus
O(5n) != 5*O(n).amit
@Chiel92 Actually,
O(n) is a set of functions, not algorithms, and it is not limited to having an algorithm with this running time. Also note, it also includes sub-linear functions.
Ivaylo Strandjev
@amit
5 *O(N) is not defined! O(N) is a set, not a value. |
You're correct, O(5n) is indeed equal to O(n). 5*O(n) doesn't make sense, O doesn't return a result, it is a notation. So you can't multiply it with a number.
Although there are some definitions where Big O is used inside formulas, for example error terms. But it has to be defined like this beforehand.
Here the wikipedia link describing O(c*n) = O(n).
1 Comment
h4ck3d
Runtime is proportional to five times the input size. How would you represent this in big-O notation?
O(5n) = 5*O(n)
As stated, this is not defined.
I suggest you (re)read at least the Wikipedia article on the subject.
"f(x) = O(g(x)) as x -> infinite" means (informal intuitive definition): "f is bounded above by g asymptotically up to a constant factor". See the article above for a formal definition.
O(5n) == O(n).
I think this is more correct ("as x -> infinite" implied): f(x) = O(x) <=> f(x) = O(5x)
Cheers!
answered Feb 27, 2013 at 16:46
Sébastien RoccaSerra
17.3k8 gold badges53 silver badges54 bronze badges
2 Comments
h4ck3d
Runtime is proportional to five times the input size. How would you represent this in big-O notation?
Sébastien RoccaSerra
I'd simply say that your function is O(n) as n -> infinite. Because if it is proportional to five times the input size, it is also proportional to the input size. So saying your function f(n) is O(5n) is equivalent to saying that your function f(n) is O(n). The later says the same thing and is simpler in my opinion.
What is 5 * { Droider }?
Without special definition of operator * for sets (or for big O notations at least), the two questions (your and mine) both does not make any sense.
Of course you can define g(n)*O(f(n)) = O(f(n) * g(n)), and then it makes perfect sense, but you have to first define it.
AFAIK, there is no standard definition for this operation.
With the above definition we get 5*O(n) = O(5*n) = O(n), and your assumption is correct.
Mathematically O(5N) != O(N) but when it comes to algorithms your care about effeciency or in other words the complexity of the algorithm, so you care more about the varaible N so O(5N) == O(N) as in equally effecient (or complex).
1 Comment
amit
Mathematically,
O(5N) = O(N) by definition of big-O notation. (Well, not exactly by definition, but you can prove it in about 2 lines)what matters in variables growth rates. Adding, Substracting, Multiplying or divising by any Constant number doent change them.
Thus any constant is insignificant and can be ommited without losing accuracy.
Regarding your question - O(5n) = O(n) = 5*O(n)
5 * { Droider }? Without special definition ofoperator *for sets (or for big O notations at least), the two questions (your and mine) both does not make any sense. Of course you can defineg(n)*O(f(n)) = O(f(n) * g(n)), and then it makes perfect sense, but you have to first define it. AFAIK, there is no standard definition for this operation.