0

Question: You have found empirically that the implemented sorting methods $A$ of complexity $\Theta(n^3)$ and $B$ of complexity $\Theta(n^2 \log n)$ spent $2$ and $10$ time units, respectively, to sort an array of $100$ objects. Find out how many time units will each algorithm spend for sorting an array of $1\,000\,000$ objects?

For this question can I say that the time spent by these implementations can be written as $T_A(n) = c_A n^3$ and $T_B(n) = c_B n^2 \log n$, therefore continue to solve $c$ using given numbers?

User426190
  • 53
  • Why do your expressions for $T_A$ and $T_B$ not match the complexities you are given? Yes, you can then solve for $c_A$ and $c_B$ but you don't need to. MathJax hint: if you put a backslash before common functions you get the correct font and spacing, so \log n gives $\log n$ – Ross Millikan Mar 15 '18 at 05:11
  • sorry, it's a typo. Will fix right away. Sorry for the confusion. – User426190 Mar 15 '18 at 05:12
  • @RossMillikan When you said "Yes, you can then solve for $c_A$ and $c_B$ but you don't need to." How would I get the time for which each of the algorithms would spend for sorting an array of 1000000 objects? – User426190 Mar 15 '18 at 05:19
  • Use the ratios as shown by Kumar Ayush. The $c$s divide out when you take the ratio of the functions of the number of items. – Ross Millikan Mar 15 '18 at 05:25

2 Answers2

0

If you are just finding an approximate time, then

$\cfrac{t1}{t2} = \cfrac{(n_1)^3}{(n_2)^3}$

$\cfrac{t1}{t2} = \cfrac{(n_1)^2 \log n_1}{(n_2)^2 \log n_2}$

Why approximate?

Because this theta notation just gives assymptotic behaviour.
In above calculation i have assumed that $k*n^3$ is the number of operations in first case, which is not exactly true. It can have lower degree terms also.

kayush
  • 2,441
0

As stated, this question has no solution. Possibly the intent is to work with constants as you suggest. However, an algorithm that takes $$ T_{A,1}(n) = \begin{cases} 2 & \text{if }n < 10^{10} \\ n^3 & \text{if } n \ge 10^{10}\end{cases} $$ steps is still a $\Theta(n^3)$ algorithm, as is $$ T_{A,2}(n) = \begin{cases} 2(n/100)^3 & \text{if }n \ne 1\,000\,000 \\ 47 & \text{if } n = 1\,000\,000\end{cases} $$ or any other number of possibilities. Both $T_{A,1}(n)$ and $T_{A,2}(n)$ satisfy $T_{A,i}(n)=2$, so they're possibilities for $T_A$, but they have different values at $1\,000\,000$, and in particular you can set $T_{A,2}(1\,000\,000)$ to be anything you like with a trivial modification.

Misha Lavrov
  • 142,276