3
$\begingroup$

I'm working on an algorithm and I'm trying to figure out its time complexity given the operations it takes to complete a input set of specific length, I have been testing the algorithm with varying input lengths.

The results shows that every time I double the input length, it takes 4 times more operations than before to complete:

  • 20 items = 1M (M=million)
  • 40 items = 4M
  • 80 items = 16M
  • 160 items = 64M
  • 320 items = 256M
  • 640 items = 1024M

What is the time complexity/running time that fits better with the above results?

$\endgroup$
  • $\begingroup$ What is the time complexity that fits better Better than what? With n the number of items, the number of operations seems to be somewhere between n and two to the power of n. $\endgroup$ – greybeard Sep 2 '16 at 6:42
5
$\begingroup$

Recurrent equation: $$T(n) = 4 \cdot T(\frac{n}{2})$$ $$T(1) = O(1)$$ Its solution: $$T(n) = \Theta(n^2)$$

$\endgroup$
  • $\begingroup$ Hi @hekto, plotted it and matches perfectly :), thanks! $\endgroup$ – Jesus Salas Sep 2 '16 at 6:55
  • 1
    $\begingroup$ This is guesswork. A finite sample can not be used to infer asymptotic properties. $\endgroup$ – Raphael Sep 2 '16 at 18:34
  • $\begingroup$ @Raphael, I simplified the question and the data provided, thanks for the heads up $\endgroup$ – Jesus Salas Sep 2 '16 at 20:09
  • $\begingroup$ @Jesus Salas - Rafael means that a normal way to analyze an algorithm is to accurately count its operations. Also, algorithms can work differently on different data - so, we normally look for worst case and average case scenarios. $\endgroup$ – HEKTO Sep 2 '16 at 21:43
  • 1
    $\begingroup$ @JesusSalas You may be interested in this answer. $\endgroup$ – Raphael Sep 3 '16 at 9:55
3
$\begingroup$

Unless you are promised that this pattern continues ad infinitum, you can not conclude anything. Asymptotic properties can not be inferred from finite samples, ever.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.