12:38 AM
2

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... 22 hours later… 11:04 PM 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 0$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 ...