While I'm checking the solution of the problem mentioned below, I could not figure out the steps to go from each step. I would like to know what are the detailed steps to go from each step of the solution ? and also where can I find a book or a source to learn think kind of equation resolving
Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n , insertion sort runs in 8n² steps, while merge sort runs in 64n lgn steps. For which values of n does insertion sort beat merge sort?
First you divide both sides by $8n$ giving $$n \lt 8 \lg n$$ Then you raise $2$ to the power of each side $$2^n \lt 2^{8 \lg n}=(2^{\lg n})^8=n^8$$ The last step is just by evaluation. We know $2^n$ will eventually get larger than any given power of $n$. We just need to compute where it happens. Here it is $43$