# running time of algorithm given time complexity

c) Suppose that algorithms A1 and A2 have computational complexities of $O(n \log(n))$ and $O(n^3)$ respectively. Both algorithms take approximately $100$ seconds to run on data input of size $n = 10,000$. Determine (to the nearest second) the time it will take each algorithm to run on data input of size

i. $n = 1,000$

ii. $n = 100$

I've been trying for the past few days to find some way to solve this but I'm completely stuck. Someone else had a similar problem but when I tried to use their method it didn't work. Please help I have an exam in this on Tuesday

• First, the big-Oh notation only gives upper bounds. As far as we are told, both algorithms may run in linear time. Second, $f_1(n) = k_1 n \log(n)$ and $f_2(n) = k_2 n \log(n) + 99$ are both $O(n \log(n))$, but, if $f_1(10^4) = f_2(10^4) = 100$, then $k_1 = 100 k_2$ and their run times for $n=10^3$ or $n=10^2$ will be very different. – Fabio Somenzi Apr 27 '18 at 16:23

Let's call the runtimes for an input of size $n$ $A_1(n)$ and $A_2(n)$ respectively. We are given that $A_1(n) = O(n\log(n))$ which means that $\lim_{n \to \infty}\frac{A_1(n)}{n\log(n)} < \infty$. Therefore the limit is finite but we don't know what it is yet. We can figure it out by using the additional information we are given: $A_1(10) = 100$. Plugging in, we get $\frac{A_1(10)}{10\log(10)} \approx 4.3429$. Doing the same for $A_2$ we get $\frac{A_2(10)}{10^3} = 0.1$.
$$\frac{A_1(1000)}{1000\log(1000)} = 4.3429 \implies A_1(1000) \approx 30\,000$$
$$\frac{A_2(1000)}{1000\log(1000)} = 0.1 \implies A_2(1000) = 100\,000\,000$$