• API
• FAQ
• Tools
• Archive
daily pastebin goal
20%
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.

Top