Asymptotic complexity little-o

44 Views Asked by At

I have a question. Let's say I have $f(n)$, $g(n)$, and $h(n)$. Then we have two algorithms, $A$ and $B$. We have $$A = f(n) + g(n)$$ and $$B = cf(n) + h(n)$$ We have $h(n) = o(f(n))$ (Little-O) and $g(n) = o(f(n))$, and also $g(n) = o(h(n))$. For example $$A = 100n + \log(n)$$ $$B = n + \log^2(n)$$

What can we say about the relationship between A and B? Is $A = o(B)$ (ie; are the different complexity levels with $B$ bounding above?) I would reason that $A = o(B)$ and that as a result $A = O(B)$ but not $A = \Theta(B)$ or $A = \Omega(B)$ because the $\log(n)$ term is polynomially bigger in $B$.

1

There are 1 best solutions below

0
On

There were no responses but I realized that bot $A$ and $B$ are $\mathcal{O}(n)$ and also the $\log^k(n)$ terms are both $o(n)$ so they are asymptotically insignificant.