joapaspe

Master Method

Jul 20th, 2012
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.66 KB | None | 0 0
  1. I tried to use the Master Method, but I wasn't able to fit the expression to this:
  2.  
  3. T(n) = a*T(n) + O(n^d)
  4.  
  5. So I tried to limit the expression this way:
  6.  
  7. T(n) = 2*T(n/2) + O(log(n))
  8.  
  9. T'(n) = 2*T(n/2) + O(1)
  10. T''(n) = 2*T(n/2) + O(n)
  11.  
  12. where T'(n) <= T(n) <= T''(n).
  13.  
  14. Given by the Master Theorem, O(T'(n)) = O(n) and O(T''(n)) = O(nlog(n)),
  15.  
  16. O(n) <= T(n) <= O(nlog(n))
  17.  
  18. Then, according to Master Teorem Case 1, I tried to fix log(n) = O(n^log_2(2-eps):
  19.  
  20. if eps = 0, O(n^log_2(2-eps)) = O(n), and with eps = 1 it would be O(n^0) = O(1).
  21. So we can figure out that exists a eps between 0 and 1 that it will be O(log(n)),
  22.  
  23. so finally the expression is O(n).
Advertisement
Add Comment
Please, Sign In to add comment