# comparing two algorithms and their respective Big O notations

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!

• 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). – patatahooligan Sep 10 '14 at 9:15

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

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.