2
$\begingroup$

I have 2 search algorithms and I have derived the following tight bound representations:

$$ nlog(n)+mlog(n) $$

$$ m∗n $$

Now i want to find a function $f(n)$ so that when $m$ is an element of tight bound $f(n)$, both algorithms have equal asymptotic run time.

Now I'm not sure if its just as simple as setting the two equations equal to each other and isolating 'm' or of it is more than tha

$\endgroup$
2
$\begingroup$

Your approach, for this problem at least, will work, but there are interesting things happening in the background. Simply setting the two terms equal and solving for $m$ will give you $$ m=\frac{n\log n}{n-\log n} $$ However, I doubt that you want to substitute this back into the two original expressions and try to find a $g(n)$ so that each of your original expressions is in $O(g(n))$. Let's try something else.

For no particular reason, let's try letting $m=\log n$. Then your two expressions become $$\begin{align} n\log n+m\log n&=n\log n+\log^2n \in O(n\log n)\text{, and}\\ n\:m&=n\log n\in O(n\log n) \end{align}$$ Hooray! If $m=f(n)=\log n$ we get a common upper bound with $g(n)=n\log n$.

Let's do the same thing, now with $m=n$. The two expressions are now $$\begin{align} n\log n+m\log n&=n\log n+n\log n \in O(n\log n)\text{, and}\\ n\:m&=n\; n\in O(n^2) \end{align}$$ Drat. No common upper bound, but by transitivity, we have $n\log n+m\log n\in O(n^2)$ and so again, we find a common upper bound, namely the asymptoticly larger $g(n)=n^2$.

You can do this for all kinds of other $f(n)$, like $f(n)=\log\log n$ and even $f(n)=1$, both of which have common solutions $g(n)=n\log n$. In fact, it seems that we can do this for any $f$ whatsoever.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.