Calculating Time Complexity for Algorithms: Understanding and Solving Problems

[EvLer]

Hello, I am trying to understand how to solve problems relating to time complexity of algorithms, esp. problems of the following kind:

An algorithm takes 0.5 ms for input size 100. How long will it take
for input size 500 if the running time is the following:
linear, nlogn, n^2, N^3

An algorithm takes 0.5 ms for input size 100. How large a problem
can be solved in 1 min if the running time is the following:
linear, nlogn, n^2, n^3

I think I have a general idea of what is asked but cannot figure out how to find it mathematically. Could someone be kind enough to explain it step by step?
Appreciate your help.

 

[Tide]

If t varies as f(n) then
$$\frac {t}{t_0} = \frac {f(n)}{f(n_0)}}$$

 

[EvLer]

Thanks a lot, I think I got the first problem type, but I still have trouble with the second. Here is how I reasoned for O(n^3):
0.5/60*10^3 = 100^3/n^3, and then I solve for n^3 and take cube root but do not come up with the right answer. What am I doing wrong?
Thanks in advance.

 

[Tide]

It looks like you didn't cube the 60 on the left hand side.

 

[EvLer]

Why do I need to cube 60?
1 min = 60*10^3(ms), it's time.
t0/t = n0^3/n^3 hence
0.5/60*10^3 = 100^3/n^3. Is that wrong? Could you then explain how this works?
Thanks again.

 

[Tide]

Oops! Sorry - I wasn't thinking - that was wrong.

What you did looks okay.

 

[EvLer]

How do I solve the case where O(nlog(base 2)n)? I know I can represent it in a different way: 2^(number/n) = n, or I can change bases where n*ln(n) = number*ln2, but how do I solve this?
Thanks for help.

 

[Tide]

The log problem is different from the others because you can't write a simple solution for it. You will have to resort to obtaining a numerical estimate. For example, you could use successive approximations which means you find a value of N which is too small and one that is too large then pick a point in between and see if that's too large or small. Adjust your range appropriately and repeat until you have the desired accuracy.