I have a function $f(x) = \cos(x)$.

I am given $\lim_{x \to 0} \cos(x) = 1$.

Is it correct to say $f(x)$ is of order $n^2$? What about $f(x)$ is $O(n^2)$

Or should I say $f(x)$ is of order $x^2$ or $f(x)$ is $O(x^2)$

I think $O(x^2)$ is correct because it depends on $x$, but this sounds awkward. I have not seen $O(x^2)$ elsewhere.

I think $O(n^2)$ is incorrect because $n$ is not defined anywhere (maybe implicitly?).

$f(x) = \cos(x)$ was just an example. If we let $g(x) = x^2$, would it be $O(x^2)$ or $O(n^2)$?


None of this is correct! For a function, Big-O describes how a function grows as it approaches infinity or some value. In your case, as x goes to $0$ so:

$$ f(x)= O(1) \text{ as } x \rightarrow 0$$

Interestingly, $ \cos(x)= O(1) \text{ as } x \rightarrow \infty$ because of the definition of Big-O. Although the function continues to oscillate between -1 and 1, not approaching anything, the definition of Big-O is that $f(x)$ is Big-O of $g(x)$ if there is some constant, $C$ such that $\lvert f(x) \rvert < C \cdot g(x)$. Now we can make $C$ any number we want. So usually we want $g(x) = 1$ to indicate a function that does not grow with $x$ so just imagine $C$ is a number just larger than $1$. We can now state $$ \cos(x)= O(1) \text{ as } x \rightarrow \infty$$

As far as using $x$ or $n$ for Big-$O$ notation, for mathematical functions, Big-$O$ describes behavior as the function approaches some value $x$ even if $x$ is $\infty$ so $x$ would be used.

In describing time complexity of computer algorithms, Big-$O$ is used to describe how the time of computation grows as the data size grows. Traditionally, the variable $n$ is used as the size of the data set so $n$ would be used. Example, average case time complexity of QuickSort is $O(n \cdot \log (n))$.

  • $\begingroup$ I understand your answer, but $f(x) = \cos(x)$ was just an example. I am asking whether to use $x$ or $n$ in Big-O notation. $O(x^2)$ or $O(n^2)$. $\endgroup$
    – qsdyebbv
    May 25 '18 at 4:27
  • $\begingroup$ Ah. For functions I believe $x$ is normal. $n$ is used in Big-O when describing computer algorithms. As in how much time increases as data size, n, grows. $\endgroup$
    – Dan Sp.
    May 25 '18 at 13:42
  • $\begingroup$ @qsdyebbv whichever one you use has to be the same on both sides of the $=$ sign. $\endgroup$ May 25 '18 at 20:14

First lets look at the definition : $f(n) = O(g(n))$ means there are positive constants c and k, such that $0 ≤ f(n) ≤ cg(n)$ for all $n ≥ k$. Simply we have to find a asymptotic upper bound in a long run (not at a point less than k).

As far your $f(x)$ is concerned i.e $f(x)=cos(x)$ We know that $cos(x)<x$ after some $x>k$ (You can see the graph). But to strenthen things $cos(x)<1 \forall x$ So it is said that $cos(x)=O(1)$.Generally speaking $O(x^2)$(after some $n>k$) is correct but not a good bound than $O(1)$ .


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.