TransWikia.com

Does $20n$ belong to $O(n^{1-epsilon})$ for some $epsilon > 0$?

Computer Science Asked on December 7, 2021

I am quite new to master theorem and I would like to ask the following question for $$?(?)=4?(?/4)+20?.$$
If there is a constant value like $20n$ does it affect the equation?

Would the equation look something like this for test case 1:

Is $f(n) = 20n in O(n^{log_ba-epsilon}) in O(n^{log_4^4-epsilon}) in O(n^{1-epsilon})$ for some $epsilon > 0$?

One Answer

Big O notation hides constant factors. In particular, for every constant $C > 0$, $$ f in O(g) Longleftrightarrow Cf in O(g). $$ In particular, for any $epsilon > 0$, $$ 20n in O(n^{1-epsilon}) Longleftrightarrow n in O(n^{1-epsilon}). $$

This follows directly from the definition of big O. Indeed, suppose that $f in O(g)$. Then there exist $N,A>0$ such that $f(n) leq Ag(n)$ for all $n geq N$. This implies that $Cf(n) leq ACg(n)$ for all $n geq N$, and so $Cf = O(g)$. Similarly, if $Cf = O(g)$ then the same argument shows that $f = C^{-1} C f = O(g)$.

Answered by Yuval Filmus on December 7, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP