Cheap and Secure Web Hosting Provider : See Now

Asymptotic growth of search algorithms

, , No Comments
Problem Detail: 

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

Asked By : Christian
Answered By : Rick Decker

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.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback