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?

, , No Comments
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

Answered By : HEKTO

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63088

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback