Midterm Study CSC321

Polynomial proofs

change all constants and add the constants

3n² + 5n = O(n²)

3n² + 5n ≤ 3n² + 5n² = 8n² → c=8, n₀=1

Exponent proof

split into 2 and multiply

2^(n+3) = O(2^n)

2³ · 2ⁿ = 8 · 2ⁿ = O(2^n)→ c=8, n₀=1

whats less than nlogn

n

whats greater than nlogn

n²

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

O(log n)

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

O(n)

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

O(n log n)

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

O(n^1.585)

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

O(n²)

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

O(n²)

if small

solve directly

such as n>1 return…

else

divide into subproblems

recurse

combine solutions

MergeSort

split in half

sort each half recursively

merge (hard part)

Quicksort

pick pivot

partition array (hard part)

recurse each side

if complete

output/return for each extension

if feasible (extension)

solve extension

pruning

Stop exploring a partial solution early when it cannot lead to a complete solution.

Subset Sum pruning

sum > T OR sum + remaining < T

LIS (Longest Increasing Subsequence)

LISbigger(i, j):

skip vs take

return max

Text segmentation

Splittable(i):

empty string → return True.

try all j≥i where

IsWord(i,j) → Splittable(j+1)