Per wiki

|f| is bounded above by g (up to constant factor) asymptotically

with this concrete example,

$$f(n) = \log n$$

$$g(n) = n^c = n^{0.000001}$$

Does "bounded above (up to constant factor)" means $f(n)$ is above $g(n)$

  • $\begingroup$ Yes, isn't that exactly what Wikipedia says? It's in the description cell for that row. $\endgroup$ – Juho May 17 '19 at 8:58
  • $\begingroup$ @Juho thank you, just to confirm my understanding is correct $\endgroup$ – shi95 May 17 '19 at 9:12

A quantity $a$ is bounded above by a quantity $b$ if $a \leq b$.

A quantity $a$ is bounded above (up to constant factor) by a quantity $b$ if there exists a constant $C>0$ such that $a \leq Cb$. (This makes sense when $a,b$ depend on some other variable).

A quantity $a(n)$ is bounded above (up to constant factor) asymptotically by a quantity $b(n)$ if there exist constants $N,C>0$ such that $a(n) \leq Cb(n)$ for all $n \geq N$. This is usually expressed as $a(n) = O(b(n))$.

| cite | improve this answer | |

"$x$ is bounded above by $y$" just means that $x\leq y$.

| cite | improve this answer | |
  • $\begingroup$ It says “up to constant factor”. $\endgroup$ – Yuval Filmus May 17 '19 at 10:34
  • $\begingroup$ @YuvalFilmus The question asks what "bounded above" means. The example sentence also includes other words but the question doesn't ask about those. $\endgroup$ – David Richerby May 17 '19 at 10:35

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.