0
$\begingroup$

So we learned in classes that some algorithms perform better at certain times. On the homework assignment, We are asked to compare algorithm 1 which takes 4n4 days to run with one that takes 3n seconds to run. The question wants us to find at what n does the first algorithm outperforms the second. The following is my attempt at solving the problem.

I first disregarded the differences between seconds and days, since whatever I multiply to each will simply be constants and be ignored when comparing the Big O notation. The first algorithm runs in O(n4), while the second runs in O(3n)

My first instinct is to set both equal to each other to find at what n does Algorithm #1 equals to Algorithm #2

1. n4 = 3n
2. log(n4) = log(3n )
3. 4 log(n) = n log(3)
4. log(n) / n = log(3) / 4

At this point I am stuck at how to continue to find n. I googled around and the cloest solution I found is to use a formula named Newton's Method , but seeing that I have no idea what that method is, I don't think I am on the right track.

Please try to reference me to hints and examples if possible, and not the solution. I really want to understand what I am doing wrong instead of just copying down the answers somewhere. Any help would be greatly appreciated!

$\endgroup$
  • 1
    $\begingroup$ Why did you disregard the constants? The question is about the one algorithm actually outperforming the other because it wants to emphasize the point that a worse algorithm complexity will cause the running time to escalate very quickly even from a very small initial value (3 seconds in the example). $\endgroup$ – patatahooligan Sep 10 '14 at 9:15
1
$\begingroup$

Any algebraic equation which can be written as $A+Bx+C\log(D+Ex)=0$ has a solution which can be expressed in terms of Lambert function.

So, the solutions of $x^4=3^x$ are given by $$x_1=-\frac{4 W\left(-\frac{\log (3)}{4}\right)}{\log (3)} \simeq 1.51678$$ $$x_2=-\frac{4 W_{-1}\left(-\frac{\log (3)}{4}\right)}{\log (3)} \simeq 7.17476$$ and then $x^4 \gt 3^x$ between these two values.

A look at the plot of $f(x)=x^4-3^x$ would have showed these results $f(1)=-2,f(2)=7$ and $f(7)=214,f(8)=-2465$.A more legible plot is the one of $g(x)=4\log(x)-x\log(3)$.

So, Newton iterations could start at $x_0=1$ for the first and at $x_0=7$ for the second.

Let me show you how it works : starting from a "reasonable" guess $x_0$, Newton method will update it according to $$x_{n+1}=x_n-\frac{g(x_n)}{g'(x_n)}$$ Let us try with $ g(x)=4\log(x)-x\log(3)$ and $g'(x)=\frac{4}{x}-\log(3)$.

For the first root, starting with $x_0=1$, the successive iterates are : $1.37865$, $1.50633$, $1.51671$, $1.51678$.

For the second root, starting with $x_0=7$, the successive iterates are : $7.17708$, $7.17476$.

$\endgroup$
0
$\begingroup$

The Newton's Method is not a formula, it won't give you an answer in one step. It's an algorithm, which belongs to a big class of algorithms to find roots of various functions.

For more info please look here.

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