How to solve some hardcore Recurrences?

Question

I am trying to solve these Recurrences for my algorithms class. Can someone please help me because Master Theorem does not work and I can not compute the sum that occurs from the tree in the first and I have not seen a good solved example for the second!

T(n) = 2*T(n/3) + n/log^2(n)

T(n) = T(n-10) + logn

Answer 1

First example is a job for Master Theorem: a=2, b=3, f=n/log^2(n). log_b(a) < 1, so it is the third case, because f(n) grows (significantly) faster than n^(log_b(a))*log^k(n) for any k. This means that main job is done outside recursion and T(n)=O(n/log^2(n)).

Second example can be solved this way:

T(n)
= T(n - 10) + log(n)
= ...
= log(n) + log(n - 10) + ...
= log(n * (n-10) * (n-20) * ...)
= [n = 10k]
= log(10^k) + log(k!)
= k*log(10) + k*log(k) - k + O(log(k))
= O(k*log(k))
= O(n*log(n))