If you want to make money online : Register now

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

, ,
Problem Detail:

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?

###### Asked By : Jesus Salas

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