Hi, I'm doing this algorithm questions and i need to find the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds. For example: f(n) = log n t = 1 seconds how do i get the largest size of n in t time?? what i did is assume log is base 10, then: lg x = y x= 10^y since: f(n) = 1,000,000 microseconds n = 10^1,000,000 am i right?? you can refer to the Q here: http://problems.datastructures.net/database/problems/compare-running-times/compare-running-times.pdf
Re: Logarithmn Well, first things first, you need to read the question a bit more carefully. The opening states clearly: Other than that, you should be on the right track.
Re: Logarithmn oh my.. tks if it's base 2, then: lg2 x = y x= 2^y since: f(n) = 1,000,000 microseconds n = 2^1,000,000 but why is the ans 10^3000000??
Re: Logarithmn Do you mean 10^{300,000} as opposed to 10^{3,000,000}? If [tex]2^{10^6}=10^x[/tex] find x.
Re: Logarithmn sorry i meant 300,000 since: 2^(10^6) = 10^x That means: since x = 10^6, therefore 10^x = 10^(10^6). but how do i get the value 10^300000??
Re: Logarithmn Not... quite. You have to take the log base 10 to isolate x, and then you get 10^6 log_10(2), or about 1000000 * log_10(2). That's the x you're looking for, and it's easy to prove that it's about 300000. Then you get that 2^(10^6) is about equal to 10^(300000).
Re: Logarithmn sorry but im actually still confuse.. i dont really understand when char.limit said i can isolate x by taking log_10 of x and i get 10^{6} . log_10 (2). i change x->y to avoid confusion. since the rule says: y = log_10 x, then x=10^{y} if we continue from 2^{106} =10^{y} then y = log_10(2^{(106)}) ???? but how did char.limit get log_10(2).10^{6}??
Re: Logarithmn Hi, i finally understood. the rule that i was looking for is log_{a}(X^{y}) = y.log_{a}(X) therefore, 2^{106} =10^{y} y = 10^{6} . log_{10}(2) However, i got another Q. if the Q was asked to use log_{2}, must we give the final ans in log_{10}??
Re: Logarithmn Yes, that's right No, it's not necessary. I'd usually leave the answer as it is unless I was specifically asked to convert it into that form.