Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- I tried to use the Master Method, but I wasn't able to fit the expression to this:
- T(n) = a*T(n) + O(n^d)
- So I tried to limit the expression this way:
- T(n) = 2*T(n/2) + O(log(n))
- T'(n) = 2*T(n/2) + O(1)
- T''(n) = 2*T(n/2) + O(n)
- where T'(n) <= T(n) <= T''(n).
- Given by the Master Theorem, O(T'(n)) = O(n) and O(T''(n)) = O(nlog(n)),
- O(n) <= T(n) <= O(nlog(n))
- Then, according to Master Teorem Case 1, I tried to fix log(n) = O(n^log_2(2-eps):
- if eps = 0, O(n^log_2(2-eps)) = O(n), and with eps = 1 it would be O(n^0) = O(1).
- So we can figure out that exists a eps between 0 and 1 that it will be O(log(n)),
- so finally the expression is O(n).
Advertisement
Add Comment
Please, Sign In to add comment