cst 370: week 2

This week, we covered asymptotic notations and sorting algorithms. Big O (O(f(n))) describes worst-case runtime, Big Theta (Θ(f(n))) the average case, and Big Omega (Ω(f(n))) the best case. For non-recursive algorithms, like checking if an array has all unique elements, we analyze time complexity directly using these notations. Recursive algorithms involve self-calls, so we identify the basic operation, set up a recurrence relation, define the initial condition, and solve it using backward substitution. For example, the recursive function S(n) = S(n-1) + n³ has multiplication as the key operation, yielding the recurrence M(n) = M(n-1) + 2, which simplifies to Θ(n).