comparing two algorithms and their respective Big O notations

Question

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 4n⁴ days to run with one that takes 3ⁿ 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(n⁴), while the second runs in O(3ⁿ)

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

1. n⁴ = 3ⁿ
2. log(n⁴) = log(3ⁿ )
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!

Answer 1

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