0
$\begingroup$

I have two recursive algorithms to solve a particular problem. I have calculated their time complexities as $O(n^2\times\log n)$ and $O(n^{2.32})$. I need to find which algorithm is better in terms of time complexity. I tried plotting graphs but two functions seem to be going together.

$\endgroup$
2
  • $\begingroup$ logn is not in the power of n. It's multiplied to n^2. $\endgroup$ Sep 27 at 2:31
  • $\begingroup$ Ok, I edited your question to make the formulas clearer. $\endgroup$
    – rici
    Sep 27 at 3:07
1
$\begingroup$

You will need to compare the rate of change for both functions. This can be accomplished by taking the derivative of both functions:

$$ O_1'(n^2 log(n)) = \frac{d}{dn} n^2 log(n) = n + 2n × log(n) $$ $$ O_2'(n^{2.32}) = \frac{d}{dn} n^{2.32} = 2.32n^{1.32} $$

Plot these derivatives and compare the graphs. If they still seem too close, continue to take higher order derivatives such as $\frac{d^2O}{dn^2}$, $\frac{d^3O}{dn^3}$, etc. Eventually, you will notice a clear difference in the rate of change.

For those who don't have access to plotting software, you can evaluate the slope of the tangent line for an arbitrarily large n-value:

$$ O_1'(10^6)=\frac{d}{dn} n^2log(n)\bigg|_{n=10^6} = 10^6 + 2(10^6) × log(10^6) ≈ 2.8631 × 10^7$$

$$ O_2'(10^6)=\frac{d}{dn} n^{2.32}\bigg|_{n=10^6} = 2.32(10^6)^{1.32} ≈ 1.9296 × 10^8$$

This means, for $n=10^6$, $O_1$'s tangent line @ $(10^6, y_1)$ would result for some equation:

$$y - y_1 = (2.8631 × 10^7)(x - 10^6) $$

and $O_2$'s tangent line would result in:

$$y - y_1 = (1.9296 × 10^8)(x - 10^6) $$

Now, the answer is clear: $O(n^{2.32})$ has a much more steeper rate of growth than $O(n^2log(n))$ for large values of $n > 10^6$. Conclusion: $O(n^2log(n))$ is more efficient than its counterpart.

$\endgroup$
1
$\begingroup$

I see, that answer is done and accepted, but let me share some thoughts:

Short answer: knowing only upper bounds it's impossible to compare algorithms. We can compare upper bounds, but this doesn't give answer to algorithms relation.

Long answer: assume we have $f\in O(n^2\log n)$ and $g \in O(n^{2.32})$. Because $\exists N \in \mathbb{N}$ such that for $n > N$ holds $n^2\log n<n^{2.32}$, then $ O(n^2\log n)\subset O(n^{2.32})$, so knowing only $g \in O(n^{2.32})$ does not gives warranty, that it is not in $ O(n^2\log n)$ also.

Let me bring analogy: if $x<5$ and $y<10$, then we cannot say how $x$ and $y$ are related to each other, without additional info. For example both variants $x=1,y=2$ and $x=2,y=1$ satisfies given conditions.

$\endgroup$
1
$\begingroup$

$O(n^{2.32})$ is kind of unusual. Do you have a mathematical proof for this, or is it an estimated based on observations? In that case, you can't draw any conclusions from it.

Big-Oh is an upper bound. So first you need to check what is the actual behaviour. If an algorithm runs in $O(n)$ then it is correct (but not very useful) to say it runs in $O(n^{2.32})$, so check that first.

If both are strict upper bounds (so the algorithms are not $o(n^2 \log n)$ and not $o(n^{2.32})$) with a little o, then the second algorithm will be slower at least for some cases if n is large. If it was $\theta$ then it would be the case for all large n.

In practice, if you want to decide which algorithm to use after you implemented them both, you would measure their execution time for their typical inputs, and find the average time and the worst time. As long as the worst time is acceptable, you'd take whichever one takes less time on average for your inputs. For example, if you need to sort a million arrays of size 10 containing almost sorted, the Big-O of the sorting algorithm is irrelevant; what counts is the average sorting time for arrays of size 10 that are almost sorted.

Quite often the execution time for small n is "fast enough". In that case you will care for cases where one or both of the algorithms are not "fast enough". So if the usual case is "fast enough", you worry more about the unusual, very large cases.

Another problem happens when the average time is low and the worst case should be very rare, but is very slow. In that case an adversary might give you inputs that run very slow. For example, Quicksort is typically fast, but for every deterministic implementation, an adversary can prepare inputs of size n that take O(n^2) time. They will never happen in practice, only when created by an adversary.

$\endgroup$
1
  • $\begingroup$ Actually, It's 2^(log 5), base 2. Thank you for your answer $\endgroup$ Sep 28 at 16:00
1
$\begingroup$

$O(n^2\log n)$ is better, since $\lim_{n \to \infty} {n^2\log n \over n^{2.32}} = 0$.

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