1
$\begingroup$

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)$

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

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))$.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It says “up to constant factor”. $\endgroup$ – Yuval Filmus May 17 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 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.