1.2. Key Aspects of Algorithms

When we study algorithms, the first thing that we need to convince ourselves is that the algorithm is correct and it is doing the job that we expected.

The correctness of an algorithm refers to its ability to produce the right outputs for all possible inputs. To ensure correctness, we often utilize formal methods to prove that an algorithm indeed fulfills its intended function under defined conditions. This involves analyzing how the algorithm behaves and verifying that it generates expected results consistently.

Think of assembling a piece of furniture from a kit. Before considering the furniture usable, you must ensure you followed the instruction manual correctly, and all screws were tightened. Similarly, correctness in algorithms means confirming that the steps of the algorithm lead to the expected outcome.

The other important aspect of algorithm is of course its efficiency. How much time does the algorithm take on inputs? Now, of course we have to factor in the size of the input.

Efficiency refers to how well an algorithm utilizes time and resources, which can significantly impact its performance, especially with large inputs. We often measure efficiency in terms of time complexity, which indicates how the runtime of an algorithm grows as the size of the input increases. Factors like input size play a crucial role in determining the overall efficiency.

Imagine you’re baking cookies. If you can bake 12 cookies in 10 minutes, how long would it take for 48 cookies? Here, you need an efficient process to manage time based on the number of cookies. In algorithms, similar calculations help us determine how well an algorithm performs as input sizes vary.

We need a notation or a way of comparing two different algorithms, which operates on the same types of inputs and produce the same type of outputs. So, this will be achieved through the concept called asymptotic complexity.

Asymptotic complexity provides a way to classify algorithms according to their performance as input size grows. This concept allows us to compare algorithms through terminology like 'Big O' notation, which describes the upper boundary of the algorithm's runtime, focusing on the most significant factors while ignoring constants and lower-order terms.

Consider two routes you can take to work: one might take 20 minutes, while another could take 35 minutes during regular traffic. However, if there’s a huge traffic jam on the longer route, it could take an hour or more. Asymptotic complexity helps assess which route (or algorithm) consistently remains faster as conditions change, much like comparing algorithms under different input sizes.

An important part of problem solving in any domain and in particular algorithms is the art of modeling the problem at a suitable level of detail.

Modeling a problem involves creating an abstract representation of the situation or challenge. This representation simplifies the problem into a format suitable for algorithmic analysis and problem solving. For algorithms, appropriate models such as graphs can effectively represent complex relationships and structures that reflect the problem at hand.

Think of a map as a model of a city. A map abstracts essential features while omitting unnecessary details. Similarly, modeling a problem in algorithms helps simplify complex scenarios into manageable components, which can then be effectively solved by algorithms.

In order to solve a problem we need to break it down into manageable sub-problems.

Decomposing problems involves dividing a large, complex problem into smaller, easier-to-solve parts. This approach makes it possible to address the individual components separately, eventually combining the solutions to resolve the overall problem effectively. The decomposition can reduce complexity and enhance the clarity of the problem-solving process.

When planning a large event, such as a wedding, you may break down tasks into manageable sections: venue selection, catering, invitations, and decoration. Tackling each section separately allows for better focus and less overwhelmed feelings, which mirrors breaking down problems in algorithms into smaller, manageable tasks.

--