Hi I'm stuck on this maths question don't really know how to about it. I've tried simultaneous equation to solve for a and b with no success. Hope you can help.
A program looks up a specific entry in a sorted list of size $n$. Suppose that the program is implemented on Computer $A$, using a linear search algorithm, and on Computer B, using a binary search algorithm. Tests are run to compare the algorithms (the run time is measured in nanoseconds):
$$\begin{array}{c|c|c}n~\text{list size}&A~\text{run time}&B~\text{run time}\\ \hline 10&70~ns&150,000~ns\\ \hline 100&340~ns&200,000~ns\\ \hline 1,000&3,040~ns&250,000~ns\\ \hline 1,000,000&3,000,040~ns&400,000~ns\\ \hline 100,000,000&300,000,040~ns&500,000~ns\end{array}$$
(i) The program run on computer $A$ has a linear growth rate of the form: $f(n)=an+b$. Find $a$ and $b$.
(ii) The program run on computer $B$ has a logarithmic growth rate of the form: $g(n)=c\ln(n)+k$. Find $c$ and $k$.
(iii) Use L'Hopital's rule to find the limit: $$\lim\limits_{n\to \infty} \frac{g(n)}{f(n)}$$
and hence determine which algorithm is more efficient for large values of $n$.
For part (i), as you say, you can find $a$ and $b$ by solving a system of equations:
We are given the following system for $A$:
$\begin{cases} 70 = 10a + b\\ 340 = 100a + b\\ 3040 = 1000a+b\\ \vdots\end{cases}$
We are told that it is linear, so we know that the same $a$ and $b$ will work for all of the equations, so we only really need to use two of them. Let us approach via the method of substitution:
$\begin{array}{lr} 70=10a+b & \text{subtract}~ 10a~\text{from each side}\\ 70-10a=b & \text{so this way of writing}~b~\text{can be used elsewhere}\\ 340=100a+b & \text{from the second equation}\\ 340 = 100a+(70-10a) & \text{by substituting our expression for}~b\\ 270 = 90a&\text{by subtracting 70 from each side and simplifying}\\ 3 = a&\text{by dividing both sides by 90}\\ 70=10a+b&\text{by going back to the first equation}\\ 70=10\cdot 3 + b & \text{by plugging in the found value of}~a\\ 40=b&\text{by subtracting 30 from each side} \end{array}$
So, we find the answer to part (i) to be $f(n)=3n+40$. Do so similarly for part (ii). Apply L'Hopital's rule and find the limit to find the answer in (iii).
The system for $B$ is:
$\begin{cases} 150000 = c\ln(10) + k\\ 200000 = c\ln(100)+k\\ 250000 = c\ln(1000)+k\\ 400000 = c\ln(1000000)+k\\ \vdots\end{cases}$
which simplifies to:
$\begin{cases} 150000 = c\ln(10)+k\\ 200000 = 2c\ln(10)+k\\ 250000=3c\ln(10)+k\\ 400000 = 6c\ln(10)+k\\ \vdots\end{cases}$
using the property of logarithms that $\ln(a^b) = b\ln(a)$