Time Complexity

T (n) = a T (n/b) + f (n)

T (n) = 2T (n/2) + n = 2[2T (n/4) + n/2] + n

= 4T (n/4) + 2n = 8T (n/8) + 3n

T (n) = 2^iT (n/2^i) + i n, log_2n≥i≥1

i = log_2n = Log[2, n]

RowBox[{T (n/2^i), =, RowBox[{RowBox[{T, (n/2^(log_2n)), Cell[]}], =, T (n/2^Log[2, n]) = T (n/n) = T (1)}]}]

T (n) = 2^iT (n/2^i) + i n = 2^(log_2n) T (n/2^(log_2n)) + n log_2n

= n T (1) + n log_2n = n T (1) + n Log[2, n]

= n log_2n + n ∈O (n log_2n)

T(n)=T(n/2)+T(n/2)+2

T (n) = 2T (n/2) + 2 = 2 (2T (n/4) + 2) + 2

= 4T (n/4) + 4 + 2

= 2^(k - 1) T (2) + Underscript[∑, 1≤i≤k - 1] 2^i = 2^(k - 1) + 2^k - 2

= 3/2n - 2 (∴n = 2^k)

T(n)=2T(n/2)+c n

T (n) = 2 (2T (n/4) + c n/2) + c n = 4T (n/4) + 2 c n

= 2^kT (1) + k c n

= a (n) + c n log n (∴n = 2^k)

T(n)=T(n-1)+n-1

T (n) = (n (n - 1))/2∈O (n^2)

C_A (n) = n + 1 + 1/nUnderoverscript[∑, k = 1, arg3][C_A (k - 1) + C_A (n - k)]

n C_A (n) = n (n + 1) + Underoverscript[∑, k = 1, arg3][C_A (k - 1) + C_A (n - k)]

(n - 1) C_A (n - 1) = (n - 1) n + Underoverscript[∑, k = 1, arg3][C_A (k - 1) + C_A (n - k)]

Underoverscript[∑, k = 1, arg3][C_A (k - 1) + C_A (n - k)] = 2[C_A (0) + … + C_A (n - 1)]

Underoverscript[∑, k = 1, arg3][C_A (k - 1) + C_A (n - k)] = 2[C_A (0) + … + C_A (n - 2)]

n C_A (n) - (n - 1) C_A (n - 1) = n (n + 1) - (n - 1) n + 2 C_A (n - 1)

n C_A (n) = (n + 1) C_A (n - 1) + 2n

(C_A (n))/(n + 1) = (C_A (n - 1))/n + 2/(n + 1)

(C_A (n))/(n + 1) = (C_A (n - 1))/n + 2/(n + 1)

= (C_A (n - 2))/(n - 1) + 2/n + 2/(n + 1) = (C_A (n - 3))/(n - 2) + 2/(n - 1) + 2/n + 2/(n + 1)

= (C_A (1))/2 + 2Underoverscript[∑, k = 3, arg3] 1/k = 2Underoverscript[∑, k = 3, arg3] 1/k

Underoverscript[∑, k = 3, arg3] 1/k≤∫_2^(n + 1) 1/xx = log_e (n + 1) - log_e2

(C_A (n))/(n + 1) = 2Underoverscript[∑, k = 3, arg3] 1/k

C_A (n) ≤2 (n + 1)[log_e (n + 2) - log_e2] = O (n log n)