Name: Anonymous 2010-03-01 17:10
Hello /sci/,
I was reading a book on the analysis of algorithms at the library today, and I had some time so I was doing the exercises. One of the questions was:
Suppose program A takes (2^n)/1000 units of time and prgram B takes 1000 * n^2 units. For what values of n does program A take less time than program B?
None of the mathematics I could remember got me to a stage where I could work out the value of n. The only options I could think of was a) taking a guess and then improving it iteratively or b) ask wolfram alpha.
Doing it iteratively, I get n = 30, since I wanted a non-negative integer and asking wolfram alpha to "solve 1000 * n ^ 2 = 2 ^ n / 1000" gives me some answer involving "the analytic continuation of the product log function" which I don't understand :(
So what I would like to know is, is there a simple way to get the answer algebraicly that I have missed? Help and/or abuse welcome.
I was reading a book on the analysis of algorithms at the library today, and I had some time so I was doing the exercises. One of the questions was:
Suppose program A takes (2^n)/1000 units of time and prgram B takes 1000 * n^2 units. For what values of n does program A take less time than program B?
None of the mathematics I could remember got me to a stage where I could work out the value of n. The only options I could think of was a) taking a guess and then improving it iteratively or b) ask wolfram alpha.
Doing it iteratively, I get n = 30, since I wanted a non-negative integer and asking wolfram alpha to "solve 1000 * n ^ 2 = 2 ^ n / 1000" gives me some answer involving "the analytic continuation of the product log function" which I don't understand :(
So what I would like to know is, is there a simple way to get the answer algebraicly that I have missed? Help and/or abuse welcome.