I have a problem in my algorithms class that I am unable to solve without using brute force. I'd love to relearn how to solve this (I took my math over a decade ago!)
There's a insertion sort algorithm that runs in 8n2 (8 n-squared) and a merge sort algorithm that runs in 64nlgn (64 n log-base2 of n). For which n does insertion sort run faster than merge sort?
I've started with the equation 8n2 < 64nlgn and simplified this to n<8lgn. With brute force I've discovered this to be true when n<= 43, but the many steps I've tried to solve this equation for n have failed.