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?

Improve this question
$\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

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ Hi @hekto, plotted it and matches perfectly :), thanks! $\endgroup$
    – Jesus Salas
    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$
    – Jesus Salas
    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.

Improve this answer
$\endgroup$
0

Your Answer

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

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