Algorithm Running Time

71 Views Asked by At

Given an algorithm with a running time $$T(n)=5T(n/2)+n^2$$

So the number of nodes at a depth $i$ would be: $5^i$

The input size for each node at $i$ would be: $n/2^i$

Agreed.

Then it states that the work at a depth $i$ is: $5^i \times (n/2^i)^2$

My understanding is that it should be the #nodes at a given depth times the input size for each node.

Why has the input size been squared in working out the total work for a given depth? Am I missing something?

1

There are 1 best solutions below

3
On BEST ANSWER

The squaring comes from the $n^2$ term in your recurrence. At each depth you actually only count these $n^2$ terms.