Recommended resources
The freely available resources this lesson will direct you to.
Welcome to a new module! We've spent the last several weeks building a solid foundation in the C programming language, covering everything from variables and loops to pointers and file handling. With those tools at your disposal, we are now ready to shift our focus from the how of programming to the what and why of problem-solving.
This lesson marks the beginning of our journey into the world of algorithms. We'll start at the very beginning by asking two fundamental questions: What exactly is an algorithm? And, if modern computers are incredibly fast, why should we care so much about making our algorithms efficient? By the end of our session, you will be able to define what an algorithm is and explain why its efficiency is one of the most crucial concepts in computer science.
1. What is an Algorithm?
At its heart, an algorithm is simply a recipe: a finite sequence of well-defined, computer-implementable instructions to solve a class of problems or to perform a computation.
To get a more formal understanding, let's explore the key qualities that make a set of instructions a proper algorithm.
Algorithm Efficiency: AP® Computer Science Principles Review
This article from Albert.io provides a concise definition and uses a helpful analogy.
Read the section titled "What Is an Algorithm?". Pay close attention to the three qualities of a good algorithm: clarity, effectiveness, and finiteness. The sandwich-making example is a simple but effective illustration of these principles.
Now, let's watch a short video that brings this definition to life. It uses a simple problem—counting people in a room—to demonstrate how we can express an algorithm and begin to think about its design.
What's an algorithm? - David J. Malan
This TED-Ed video, "What's an algorithm?", offers an excellent and accessible introduction.
Watch from the beginning until the end of the first example. Notice how the problem is translated into pseudocode, which is a way of describing an algorithm using plain language that resembles a programming language. This allows us to focus on the logic without worrying about the specific syntax of C.
As you saw, an algorithm provides an unambiguous, step-by-step process that guarantees a correct result for a given problem.
2. The Importance of Efficiency
The video you just watched ends with a critical question: "Can we do better?" This question is the driving force behind the study of algorithms. While a simple algorithm might be easy to understand, it may not be practical for large-scale problems.
You might wonder, with processors that perform billions of operations per second, does it really matter if one algorithm takes a few more steps than another? The answer is a resounding yes, especially in the modern world of big data.
Let's hear why this is the case.
Algorithms Explained for Beginners - How I Wish I Was Taught
The video "Algorithms Explained for Beginners" directly addresses why speed is so critical.
Please watch the segment from Why speed matters. The speaker explains how the scale of data at companies like Google and Facebook makes algorithmic efficiency essential.
The key takeaway is that efficiency isn't about saving a few nanoseconds on your personal computer. It's about the difference between a problem being solvable in a few minutes versus taking longer than the age of the universe. An inefficient algorithm can render a program useless when the input size—whether it's users, transactions, or data points—grows.
This isn't just a concern for massive tech companies. Efficient algorithms power many of the applications you use daily.
Algorithm Efficiency: AP® Computer Science Principles Review
This section of the Albert.io article provides tangible examples.
Read the section "Examples of Algorithm Efficiency in Real Life". As you read, think about your own experience with these technologies. A slow search engine or a lagging social media feed is often the result of an underlying inefficient algorithm.
3. Visualizing the Difference in Efficiency
To make this more concrete, let's consider a simple problem: finding a specific page in a book.
Imagine you have a 1,000-page book and you need to find page 750.
- Algorithm A (Linear Search): Start at page 1, check if it's page 750. If not, go to page 2, check again, and so on, until you find it. In the worst case (if you were looking for page 1000), you would have to check all 1000 pages.
- Algorithm B (Binary Search): Open the book to the middle (page 500). Since 750 is greater than 500, you know your page is in the second half. You can discard the first 500 pages. Now, you open to the middle of the remaining half (page 750). You found it in just two steps.
This simple analogy demonstrates the profound impact of choosing the right algorithm.
The difference between these approaches becomes even more dramatic as the input size increases. Computer scientists have a way to classify this growth. We'll dive deep into this in the next lesson, but for now, let's look at a visual comparison.
Categorizing an algorithm's efficiency | AP CSP (article)
This Khan Academy article does an excellent job of visualizing and explaining the practical consequences of different efficiency classes.
First, look at the graph under the heading "All together now". This graph is one of the most important in computer science. It shows how drastically different types of algorithms scale. Notice how the lines for n² and 10ⁿ shoot upwards, while log₂(n) and n grow much more slowly. Next, read the section "Polynomial vs. superpolynomial" and study the accompanying table. This section introduces the crucial concepts of reasonable (polynomial) and unreasonable (superpolynomial) run times. The table powerfully illustrates why an algorithm's classification matters more than the raw speed of the computer running it.
The distinction between "reasonable" and "unreasonable" time is the core reason we study algorithmic efficiency. An inefficient algorithm for a non-trivial problem is often not a solution at all, because the resources required to run it are simply not available.
Conclusion
In this lesson, we've made a pivotal transition from the mechanics of coding to the theory of problem-solving. You now have a foundational understanding of what algorithms are and, more importantly, why their efficiency is a primary concern for any software developer.
Key Takeaways:
- An algorithm is a clear, finite set of steps for solving a problem. It must be correct and unambiguous.
- Efficiency measures how an algorithm's use of resources (like time or memory) scales as the size of the input (
n) increases. - The importance of efficiency is driven by massive datasets. An inefficient algorithm can quickly become "unreasonable," taking impractical amounts of time to run.
- The goal of algorithm design is often to find a "reasonable" (polynomial time) solution for a problem, as "unreasonable" (superpolynomial time) solutions are often infeasible in practice.
Preview of the Next Lesson:
We've seen that some algorithms are dramatically more efficient than others. But how do we formally describe and compare them? In our next lesson, we will introduce Big-O notation, the standard language used in computer science to classify the efficiency of algorithms. This will give us the analytical tools to evaluate the code we write and make informed decisions about how to solve problems effectively.