CST 370 - Week 2 Journal

Asymptotic Notations:

Provides a formal way to describe how an algorithm's running time grows as the input size increases. Instead of focusing on exact execution times, which depend on hardware and implementation details, these notations allow us to compare algorithms based on their growth rates. Big-O notation describes an upper bound, helping understand the worst-case scenario. Big-Omega gives lower bound and Big Theta captures a tight bound, showing when upper and lower bounds match. 

Analysis of Non-Recursive Algorithms:

Focuses on determining running time by counting how often a key operation executes. This usually involves analyzing loops and converting them into summation expressions. Nested loops are especially important since they often lead to polynomial time complexities. Basic operation - dominates running time and expressing its frequency as a function of input size. 

Analysis of Recursive Algorithms:

Require different analysis approach using recurrence relations. Recurrence relations is how a problem of size n depends on smaller instances. Structure of recursion - how many recursive calls are made and how the input size changes. 

Brute-Force Algorithm Design:

Solve problems by trying all possibilities or following the most straightforward approach. EX: selection sort or bubble sort - which illustrate how brute force is east to design and reason about but can be inefficient.