получить замкнутую форму уравнения рекурсии и сравнить, что быстрее

Question

Получите замкнутую форму этих уравнений, если это возможно.Затем определите, что будет быстрее, чем другое.

f(n) = 0.25f(n/3)+ f(n/10) + logn, f(1) =  1

g(n) = n + log(n-1)^2 + 1

В этих уравнениях я должен расширить эти рекурсии и попытаться обнаружить закономерности внутри?Я действительно не знаю, как вычислить закрытую форму интуитивно

Answer 1

Краткий ответ: g(n)>f(n) Длинный ответ: g даже не рекурсивен, поэтому вы сразу видите, что g (n) = O (n). Вы можете приблизительно f(n) <f(n/2)+logn которая по основной теореме является & theta; (logn)