Computer Science Asked by aviv barel on February 13, 2021
You are given two algorithms $A$ and $B$, with worst-case time complexity $f_A(n)$ and $f_B(n)$, respectively.
Assume:
(i) For each $n$ there exists an input $x$ of size $n$ such that the number of steps of algorithm $A$ on $x$ is half the number of steps of $B$ on $x$.
(ii) $f_A(n) = Omega(h(n))$ for some positive function $h(n)$.
Explain your answers.
You are essentially asking the following question:
Suppose that $f(n) geq g(n)$ for some $n$. Is there a universal constant $C$ such that $min_n f(n) geq C min_n g(n)$?
Hopefully this formulation makes it easier to answer.
Answered by Yuval Filmus on February 13, 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