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$?
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
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP