Approaching Problems & Algorithm Complexity

Approaching Problems

When faced with a new programming problem, it's common to feel overwhelmed. Effective strategies can help in developing algorithmic solutions. Here are three key strategies:

1. Breaking the problem into smaller sub-problems: Decompose the complex task into manageable parts that can be solved independently. After solving the individual parts, you can assess the global problem or iteratively break down other sub-problems. Sometimes, this involves finding a self-similar problem that's easier to solve, leading to recursion.
2. Transforming the Problem: Algorithm design often involves recognizing problem patterns and converting the specific problem into a generic one with a known solution. Identifying these patterns improves with experience and can be used by programmers from beginner to expert. For example, finding the oldest user can be transformed into a minimum/maximum aggregation problem (finding the maximum value in a list of user ages). If the users' data is stored as date of birth, the problem can be broken down into two steps: calculating ages and finding the maximum age. If a precise transformation isn't possible then finding a close generic problem and adapting its solution can be helpful. Common generic problems are sorting and searching.
3. Creating Traces: When you can't decompose the problem further or recognize a generic pattern, manually work through the steps to solve the problem using specific data inputs. Pretend you are explaining your process to a robot and write down each step explicitly. These traces can reveal decisions and process steps that can be converted into a flowchart. Also, you can identify a generic pattern previously missed. Manual traces provide input/output pairs for testing your program.

Algorithm Complexity

While multiple algorithms can solve a problem correctly, time complexity is also important. Time complexity measures how efficient an algorithm is based on the number of instructions a computer executes to get a result. You should aim for algorithms with the lowest possible complexity to minimize computation time and hardware resource use. Some algorithms are theoretically correct, but their time complexity is so high that they're impractical. Understanding complexity analysis is essential for determining when to abandon a correct algorithm for a more efficient one.

Complexity Analysis

Complexity analysis quantifies an algorithm's time and space complexity. The complexity is expressed in terms of the input, describing how the time/space grows as a function of the input. We are usually interested in the worst-case time complexity, which is the time taken in the