# Calculating complexity

1. Sep 19, 2004

### 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?

2. Sep 19, 2004

### Tide

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

3. Sep 19, 2004

### 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?

4. Sep 19, 2004

### Tide

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

5. Sep 19, 2004

### 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.

6. Sep 19, 2004

### Tide

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

What you did looks okay.

7. Sep 19, 2004

### 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.

Last edited: Sep 19, 2004
8. Sep 20, 2004

### 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.