TransWikia.com

If $B$ is worse than $A$ on some inputs, how do their worst-case time complexities compare?

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

  • Is it possible that $f_B(n) = Omega(h(n))$
  • Is it necessary that $f_B(n) = Omega(h(n))$?

Explain your answers.

One Answer

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

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