Cheap and Secure Web Hosting Provider : See Now

Order Notation - Why can't $c$ be in terms of $n$?

, , No Comments
Problem Detail: 

For $f(n)$ to be in $O(g(n))$, there must exist a $c > 0$ and $n_0 > 0$ such that

$$0 \leq f(n) \leq cg(n) \text{ for all }n \geq n_0\,.$$

I found a solution to a question where my $c$ is in terms of $n$, but my friend says you can't have that. I'd like to understand why. My thought process is: if I am given an $n$, I can pick a distinct $c$ that will satisfy the requirements above by using the $c$ in terms of $n$ relationship.

Thank you.

Asked By : Chara
Answered By : David Richerby

Suppose we define $f(x) = O'(g(x))$ to mean that there is a function $c(x)$ such that $f(x)\leq c(x)g(x)$ for all sufficiently large $x$. Then $f(x) = O'(g(x))$ for almost every pair of functions $f$ and $g$, just by taking $c(x)=f(x)$. So, this definition just isn't a useful way to compare functions.

(I say "almost every pair" because there are issues if we have infinitely many values of $x$ for which $g(x)=0$ and $f(x)\neq 0$ but I don't think it's worth pinning down exactly what functions work and what don't.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57195

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback