Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

The source of this question comes from an undergraduate course I am taking, which covers an introduction to the analysis of algorithms. This is not for homework, but rather a question asked in CLRS.

You have a slow machine running at $x$ MIPS, and a fast machine running at $y$ MIPS. You also have two algorithms of the same class, but different running time complexities: one "slow" algorithm runs at $T(n) = c_1n^2$ whereas a "fast" algorithm runs at $T(n) = c_2n \log n$.

You execute the slow algorithm on the fast machine, and the fast algorithm on the slow machine. What is the largest value of n such that the fast machine running the slow algorithm beats the slow machine running the fast algorithm?

My solution so far:

Find the set of all $n$ such that $$\frac{c_2n\log n}{x} > \frac{c_1n^2}{y}$$ where $n$ is a natural number.

This is my work thus far:

$$\{n : \frac{c_2 n \log_2 n}{x} > \frac{c_1 n^2}{y}, n \in \mathbb{N}\} = \{n : n < \frac{c_2 y}{c_1 x} \log_2 n, n \in \mathbb{N}\}$$

The only solution that comes to mind now is to plug-n-chug all values of $n$ until I find the first n where

$$n < \frac{c_2y}{c_1x}\log(n)$$

no longer holds.

share|improve this question
3  
This is really more a question of mathematics than a question of computer science. If you replace $n$ with $x$ then you have a transcendental equation over the reals, which you can't really reduce to a closed-form solution for $x$. Once you find an $x$, your answer is $x$ rounded down to the nearest integer. In other words, "plug-n-chug" or "guess-and-check" is just about as good as you can do in the general case. This usually manifests as either graphical or numerical methods. –  Patrick87 Sep 18 '12 at 15:40
add comment

1 Answer

Consider your last inequality:

$\qquad \displaystyle n < \frac{c_2y}{c_1x}\log(n)$

Now, $C\log n$ with $C = \frac{c_2y}{c_1x}$ is a concave function. Therefore, there are at most two intersections, and only one of them is interesting for you; that is, solve

$\qquad \displaystyle n = C\log(n)$

and find out which algorithm is faster in which interval by simply calculating the respective function values at some point in the respective interval.

It is true that solving this equality explicitly is hard/impossible. For some fixed $C$, computer algebra gives you an expression in a well-known function; interesting (real) intersection turns out to be at

$\qquad \displaystyle n = e^{-W_{-1}(-\frac{\ln 2}{C})}$

if $C \geq e \ln 2$, with $W_k$ the analytic continuation of the product log function. This function does not have a nice closed form, but it can be evaluated numerically for given $C$; for instance, you get $\approx 116,74$ for $C=17$.

share|improve this answer
    
Just making sure: did you interpret my equation as having the natural log or log-base-2? I should clarify that every instance of log(n) is of base 2, and will modify the question appropriately. –  torik Sep 19 '12 at 13:30
    
In CS, we usually use $\log = \log_2$, whereas mathematicians assume $\log = \ln$. Therefore, where I use $\log$ it's to base $2$, exceptions are noted. This is (probably) where $\ln 2$ comes from in the result. –  Raphael Sep 19 '12 at 21:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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