You can try to apply the Masters theorem or use a recursion tree. You can also try to unfold the recurrences, as we saw with T(n) = T(n 1) + O(n) in lecture. Another technique is applicable if the work term is not a polynomial: 1) take the polynomial upper bound of it, and see what Master theorem gives you, 2) take the polynomial lower bound of it, and see what Master theorem gives you

) T(n) = T(n2) +logn