Week 2 Learning Journal - CST370

This week covered asymptotic notations and algorithm analysis, which felt math-heavy at first but started making sense once I applied it to my homework.

The textbook reading explained the three main notations: Big-O for worst-case upper bounds, Big-Omega for best-case lower bounds, and Big-Theta for when both are the same. I found the Theta notation video helpful because it showed concrete examples of when to use each one.

The best part of this week was seeing how analysis applies to real code through both homework problems.

HW2_1 (Closest Pair Problem): I needed to find the minimum distance between any two numbers in an array. The brute force approach would compare every pair, which takes quadratic time. Instead, I sorted the array first and then scanned consecutive elements. This is much faster because sorting takes n log n time and scanning takes linear time. After sorting, the minimum distance must be between adjacent elements, so I only needed one pass through the array.

HW2_2 (Range Compression): This problem required displaying sorted numbers using shorthand for consecutive sequences. For example, instead of printing "1 2 3 4 5 6 7", we print "1-7" to save space. The algorithm also relies on sorting first, then a single linear pass to identify where consecutive ranges start and end. Both problems share the same overall time complexity because sorting is the slowest step in both cases.

Recursive Analysis

The backward substitution method was new to me. It involves expanding a recurrence relation multiple times until you see a pattern, then solving for the closed form. It takes practice but helps analyze recursive functions.

Brute Force Design

I learned that Brute Force is not always bad. It is simple and sometimes good enough for small inputs. But understanding its quadratic time limitations helps me know when to look for smarter solutions like sorting.