# What does “bounded above” mean in Family of Bachmann–Landau notations?

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

• Yes, isn't that exactly what Wikipedia says? It's in the description cell for that row. – Juho May 17 at 8:58
• @Juho thank you, just to confirm my understanding is correct – shi95 May 17 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))$$.

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

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