Does every algorithm for performing multiplication of binary strings of length $n$ has a runtime complexity that is $\Theta(n^2)$?
Give an example of a function that is $\mathcal{O}(n^3)$ but not $\Theta(n^3)$
Given functions $f$ and $g$, if both $f = \mathcal{O}(g)$ and $g = \mathcal{O}(f)$ then we write $f = \Theta(g)$.
I want to say no since for example Karatsuba multiplication is $\mathcal{O}(n^{log_2(3)})$
I don't know about number 2.
Any help will be appreciated.