Как я могу дать T (n) в асимптотических обозначениях для рекурсий?

Question

мне нужно дать Т (п) в асимптотической нотации для следующих рекурсии:

T(n) = 2T(n/2) + *big_omega(n) 
T(n) = T(n-1) + *big_omega(n) 

И возможно объяснить рассуждения? Благодаря

Answer 1

использования мастер-теорема

1) п = О (п^log_n (п)) -> Случай 1

Применение разворачивая

2) T (N) = Т (п -1) + O (n)

T (n-1) = T (n-2) + O (n-1) -> T (n) = T (n-2) + O (n- 1) + O (n)

...

попытаться сформировать форму нерекурсивной формулы