<= vs < when proving big-o notation
Posted
by
user600197
on Stack Overflow
See other posts from Stack Overflow
or by user600197
Published on 2011-02-02T15:24:46Z
Indexed on
2011/02/02
15:25 UTC
Read the original article
Hit count: 171
big-o
We just started learning big-o in class. I understand the general concept that f(x) is big-o of g(x) if there exists two constants c,k such that for all x>k |f(x)|<=c|g(x)|. I had a question whether or not it is required that we include the <= to sign or whether it is just sufficient to put the < sign?
For example: suppose f(x)=17x+11 and we are to prove that this is O(x^2). Then if we take c=28 and x>k=1 we know that 17x+11<=28x^2. So since we know that x will always be greater than 1 this implies that 28x^2 will always be greater than 17x+11. So, do we really need to include the equal sign (<=) or is it okay if we just write (<)?
Thanks in advance.
© Stack Overflow or respective owner