# what is the time complexity for an algorithm that operations to complete grows by 4 when doubling the input length?

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?

• 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. Sep 2, 2016 at 6:42

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

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

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.