f(n) = log n t = 1 seconds


by nuttynibbles
Tags: logarithm
nuttynibbles
nuttynibbles is offline
#1
Feb3-12, 11:30 PM
P: 7
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/d...ning-times.pdf
Phys.Org News Partner Mathematics news on Phys.org
Pseudo-mathematics and financial charlatanism
Overcoming structural uncertainty in computer models
A new mathematics for experimental science
Char. Limit
Char. Limit is offline
#2
Feb3-12, 11:32 PM
PF Gold
Char. Limit's Avatar
P: 1,930
Quote Quote by nuttynibbles View Post
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/d...ning-times.pdf
Well, first things first, you need to read the question a bit more carefully. The opening states clearly:

Note that log n means the logarithm in base 2 of n.
Other than that, you should be on the right track.
nuttynibbles
nuttynibbles is offline
#3
Feb3-12, 11:38 PM
P: 7
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??

Mentallic
Mentallic is offline
#4
Feb4-12, 12:01 AM
HW Helper
P: 3,433

f(n) = log n t = 1 seconds


Quote Quote by nuttynibbles View Post
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??
Do you mean 10300,000 as opposed to 103,000,000? If

[tex]2^{10^6}=10^x[/tex]

find x.
nuttynibbles
nuttynibbles is offline
#5
Feb4-12, 12:07 AM
P: 7
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??
Char. Limit
Char. Limit is offline
#6
Feb4-12, 12:09 AM
PF Gold
Char. Limit's Avatar
P: 1,930
Quote Quote by nuttynibbles View Post
sorry i meant 300,000

since:
2^(10^6) = 10^x
That means:
10^(2^(10^6)) correct. but how do i calculate the value 10^300000?? i'll get error on my calculator
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).
nuttynibbles
nuttynibbles is offline
#7
Feb4-12, 12:16 AM
P: 7
hi char.limit, may i know which log rule define this??
Mentallic
Mentallic is offline
#8
Feb4-12, 03:06 AM
HW Helper
P: 3,433
Quote Quote by nuttynibbles View Post
hi char.limit, may i know which log rule define this??
If

[tex]a^b=c[/tex]

then

[tex]b=\log_ac[/tex]

So can you apply this to your example?
nuttynibbles
nuttynibbles is offline
#9
Feb4-12, 09:26 AM
P: 7
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 106 . log_10 (2).

i change x->y to avoid confusion. since the rule says:
y = log_10 x, then x=10y

if we continue from
2106 =10y
then
y = log_10(2(106)) ????
but how did char.limit get log_10(2).106??
nuttynibbles
nuttynibbles is offline
#10
Feb4-12, 09:50 AM
P: 7
Hi,

i finally understood. the rule that i was looking for is
loga(Xy) = y.loga(X)

therefore,
2106 =10y
y = 106 . log10(2)

However, i got another Q. if the Q was asked to use log2, must we give the final ans in log10??
Mentallic
Mentallic is offline
#11
Feb4-12, 12:50 PM
HW Helper
P: 3,433
Quote Quote by nuttynibbles View Post
Hi,

i finally understood. the rule that i was looking for is
loga(Xy) = y.loga(X)

therefore,
2106 =10y
y = 106 . log10(2)
Yes, that's right

Quote Quote by nuttynibbles View Post
However, i got another Q. if the Q was asked to use log2, must we give the final ans in log10??
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.
nuttynibbles
nuttynibbles is offline
#12
Feb4-12, 09:21 PM
P: 7
hmm okay tks alot peeps


Register to reply