Course contentsShow
← Computer Science
Lesson 270 of 2,8727. Introduction to Complexity AnalysisFree lesson

What is Runtime Analysis?

Understanding why we measure algorithm efficiency and the difference between correctness and performance.

What is Runtime Analysis?

You'll learn: why we care about measuring how fast and efficiently our code runs, and how that's different from just making code work correctly.

The Difference Between Correct and Fast

By now, you've written many programs that solve problems—finding elements in arrays, reversing strings, calculating factorials. But here's an important question: does your solution just work, or does it work well?

Correctness means your program produces the right answer. If you ask it to find the maximum element in an array, it finds the maximum element.

Performance (or efficiency) means your program produces the right answer quickly and without wasting resources like time or memory.

Why Runtime Analysis Matters

Imagine two programs that both correctly sort 1,000 numbers:

  • Program A finishes in 0.01 seconds
  • Program B finishes in 10 seconds

Both are correct, but Program A is vastly more efficient. Now imagine sorting a million numbers—Program B might take hours or even crash!

Runtime Analysis is the study of how long an algorithm takes to run as the input size grows. It helps us:

  • Compare different solutions to the same problem
  • Predict whether our code will handle large inputs
  • Make informed decisions about which algorithm to use

Think of it like choosing a route for a road trip: many routes reach your destination (correctness), but some are much faster than others (performance).

Key Takeaway: Runtime analysis measures algorithm efficiency, not just correctness—it tells us how our code performs as input grows, helping us choose faster, more scalable solutions.