DSA Ch 3 & 4

asymptotic efficiency

how an algorithms running time behaves “in the limit” (as n gets very large), while abstracting away low-order terms and constant factors

asymptotic efficiency notations

• O (Big-O) - grows no faster than (<=) (upper bound for speed)

• Ω (Big-Omega) - grows no slower than (>=) (lower bound for speed)

• Θ (Big-Theta) - grows exactly as fast as (=)

highest order term

term that grows the largest as n → ∞

ex: f(n)=7n^3+100n^2−20n+6

highest order term = n³

O (Big-O)

this is un upper bound for a time complexity equation. represented by a multiplier, c, and the highest order term

Ω (Big-Omega)

this is un lower bound for a time complexity equation. represented by a multiplier, c, and the highest order term

Θ (Big-Theta)

this is un tight bound for a time complexity equation. when big 0 and omega are have the same highest order term, but different multipliers

if both O(n³) and Ω(n³), we can now say it's Θ(n³)

Recursion tree Method

The function has a recursive part and a non-recursive part. Recursive part represents the time complexity of the recursive lines in the function. The non-recursive part represents the time complexity of the non-recursive lines that are called each time the function recurses.

1. draw each level as the function calls on itself and divides

2. make a function to describe how many times the algorithm will recurse in terms of n

3. find out the time complexity of the non-recursive part at each level (if data is shrinking, plug in data size to non-recursive part to find new time complexity of that line)

4. Does the sum of the non-recursive part approach any multiple of n? That will be the time complexity. Otherwise it will = (function describing the times the algorithm will recuse)(n)

Master Method

for time complexity functions in the form of T(n)=aT(n/b)+f(n) where a>=1 and b>1.

Substitution Method

1. Guess an big O for T(n)

2. Prove that T(n)<=bigO when plugging in a value <n

   1. plug big O into the T(n) function, adjusting for the <n value, and simplify

   2. show that resulting function T(n)<=bigO

multiplying square matrices

T(n)=Θ(n³) by master method