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$
1
  • $\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, 2016 at 6:42

2 Answers 2

5
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Hi @hekto, plotted it and matches perfectly :), thanks! $\endgroup$ Sep 2, 2016 at 6:55
  • 1
    $\begingroup$ This is guesswork. A finite sample can not be used to infer asymptotic properties. $\endgroup$
    – Raphael
    Sep 2, 2016 at 18:34
  • $\begingroup$ @Raphael, I simplified the question and the data provided, thanks for the heads up $\endgroup$ Sep 2, 2016 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, 2016 at 21:43
  • 1
    $\begingroup$ @JesusSalas You may be interested in this answer. $\endgroup$
    – Raphael
    Sep 3, 2016 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$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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