SHARE
TWEET

Untitled

a guest Feb 17th, 2019 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. T(3) = T(2) + 2*T(1) + n. It uses previous base cases therefore we don't need any more base cases.
  2.  
  3. Base cases:
  4.  
  5. n=1 : T(1) = 1 $\geq$ c*1*log1 for any c
  6.  
  7. n=2 : T(2) = 1 $\geq$ c*2*log2 for c $\leq$ 1/2
  8.  
  9. Step: We show that the inequality holds for some n $\geq$ $n_0$
  10.  
  11. IH: Assume that T(k) $\geq$ c*k*log k
  12.  
  13. T(n) = T($\lceil$n/2$\rceil$) + 2*T($\lceil$n/4$\rceil$) + n    (IH on $\lceil$n/2$\rceil$ and $\lceil$n/4$\rceil$)
  14.  
  15. T(n) $\geq$ c*$\lceil$n/2$\rceil$*log$\lceil$n/2$\rceil$ + 2*c*$\lceil$n/4$\rceil$*log$\lceil$n/4$\rceil$ + n
  16.  
  17. n/2 $\leq$ $\lceil$n/2$\rceil$ and n/4 $\leq$ $\lceil$n/4$\rceil$ and n/4 < n/2
  18.  
  19. c*n/2*log(n/4) + 2*c*n/4*log(n/4) + n
  20.  
  21. c*(n/2+2*n/2)*log(n/4) + n
  22.  
  23. c*n*log(n/4) + n
  24.  
  25. c*n*logn -2*c*n + n
  26.  
  27. c*n*logn -n(2*c - 1) $\geq$ c*n*logn
  28.  
  29. -2c+1 $\geq$ 0
  30.  
  31. 2c $\geq$ -1
  32.  
  33. c$\leq$ 1/2
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top