Thread: Comparison of running times

Could one of ya'll wise programmers out there be able to tell me what this question is asking me? I couldn't figure it out and this is for my Data Structures course that I am taking:
'For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algortihm to solve the problem takes f(n) microseconds.'

------|1 second|-----|1 minute|-----|1 hour|-----|1 day|----
lg n
------|--------|------|--------|-----|------|-----|-----|----
sqrt(n)
------|--------|------|--------|-----|------|-----|-----|----
n
------|--------|------|--------|-----|------|-----|-----|----
n lg n
------|--------|------|--------|-----|------|-----|-----|----
n^2
------|--------|------|--------|-----|------|-----|-----|----
n^3
------|--------|------|--------|-----|------|-----|-----|----
2^n
------|--------|------|--------|-----|------|-----|-----|----
n!
------|--------|------|--------|-----|------|-----|-----|----

Again, I do not require the answer I just need to know what this question is asking me. Thanks a lot folks.

Some of these you can solve for n.
For example
sqrt(n) = 3600.
Solving this for n gives the value of n for the algorithm
to take 1 hour.

Others such as the factorial, n lg n you have
to use a calculator or just write a quick program to
calculate it.

Originally posted by supaben34
Could one of ya'll wise programmers out there be able to tell me what this question is asking me? I couldn't figure it out and this is for my Data Structures course that I am taking:
'For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algortihm to solve the problem takes f(n) microseconds.'

------|1 second|-----|1 minute|-----|1 hour|-----|1 day|----
lg n
------|--------|------|--------|-----|------|-----|-----|----
sqrt(n)
------|--------|------|--------|-----|------|-----|-----|----
n
------|--------|------|--------|-----|------|-----|-----|----
n lg n
------|--------|------|--------|-----|------|-----|-----|----
n^2
------|--------|------|--------|-----|------|-----|-----|----
n^3
------|--------|------|--------|-----|------|-----|-----|----
2^n
------|--------|------|--------|-----|------|-----|-----|----
n!
------|--------|------|--------|-----|------|-----|-----|----

Again, I do not require the answer I just need to know what this question is asking me. Thanks a lot folks.

It's asking to use each function as a way of calculating how large of a problem, n, can be calculated in t seconds.

f(n) = t

so sqrt(n) = 100 microseconds (or I think 100 microseconds is 1 second)

you'd have to solve by squaring both sides, so

n = 10000

which means using sqrt, a problem of size 10000 could be solved in 1 second.

Hope that makes sense!