This is a challenging question I've been trying (unsuccessfully) to solve via programming, math or both.
Suppose you're given a 2D grid, whose width and height, $w$ and $h$, can each range from $1$ thru $12$ inclusive. Each cell in this grid can be in any of $k$ states (where $k$ ranges from $2...
I have some queries in recurrence relations. Can someone help me :) http://cs.stackexchange.com/questions/69254/solving-recurrence-relations-using-substitution-followed-by-tree-method-masters
$T(n) = 4T(\sqrt n) + n$
First I substitute n = $2^k$:
$T(2^k) = 4T(2^{k/2}) + 2^k$
Now I rename the above as follows:
$S(k)=4S(k/2) + 2^k$
Now if I try to use tree method on this in the following way:
Work done at Level 1 = $2^k$
Work done at Level 2 = $2^{k/2} * 4$
Work done at Level 3 ...
$T(n) = 4T(\sqrt n) + n$
First I substitute n = $2^k$:
$T(2^k) = 4T(2^{k/2}) + 2^k$
Now I rename the above as follows:
$S(k)=4S(k/2) + 2^k$
Now if I try to use tree method on this in the following way:
Work done at Level 1 = $2^k$
Work done at Level 2 = $2^{k/2} * 4$
Work done at Level 3 ...
