I'm studying for an entrance exam and I have sample questions. One of the questions is this
Prove that recurrence $T(n) = T(n/5) + T(4n/5)+n/2$ has a solution $T(n) = \omega(n \log n)$.
Solve by drawing the recursion tree.
This is what I drew on my paper:
root: n/2 => (4n/5)/2
=> (n/5)/2
right sub tree: (4n/5)/2 => (16n/25)/2
=> (4n/25)/2
left sub tree: (n/5)/2 => (4n/25)/2
=> (n/25)/2
From what I saw online when I was searching for a solution to this question I noticed people were drawing the trees and saying Big O something as an answer. I'm wondering how do they determine that Big O notation is the correct answer for this question or if my tree is correct?