How can I calculate the time complexity for $T(n)= T(f(n)) + g(n)$ type of recurrence relations? For example: $$ T(n)= \begin{cases} 1 &n\leq 1\\ T(\log_2 n) + n & n > 1 \end{cases}$$ or $$ T(n)= \begin{cases} 1& n\leq 1\\ T(\log_2\log_2 n) + 2^n & n > 1 \end{cases}$$
I am preparing for a test so would it be possible to convert the equations somehow so that the Master theorem can be applied?
I don't think there's a general way to deal with recurrence relations with a weird $f(n)$, but in these cases it's easy to show that the $g(n)$ is what dominates: if you unwind the first recurrence, you get $$T(n)=n+\log_2 n+\log_2\log_2 n+\log_2\log_2\log_2 n + ...,$$ where the sum continues as long as the terms keep being positive. You can show by induction that if $n=2^m$ then $n\leq T(n)\leq 2n$, and that, together with the fact that $T(n)$ is increasing, is enough to show $T(n)=\Theta(n)$.