Topic 3.17 Notes – Algorithmic Efficiency

1. What a Problem Is in Computing

In computer science, a problem is a general task that can be solved with an algorithm.

• Problem = general description
  • Example: sorting a list of numbers
  • Example: determining whether a number is prime
• Instance of a problem = the problem + specific input
  • Sorting [9, 2, 5, 1]
  • Checking if 29 is prime

On quizzes, they’ll often sneak this distinction into wording. If you see specific data, that’s an instance, not the general problem.

Types of Problems

Decision Problems

A decision problem has a yes/no answer.

• “Is there a path between these two users in a network?”
• “Does this list contain a duplicate value?”
• “Is this number divisible by 7?”

You are checking whether a condition is true.

Optimization Problems

An optimization problem asks for the best solution among many possibilities.

• “What is the shortest path between two cities?”
• “What is the minimum cost way to ship these packages?”
• “What is the fastest route through all delivery stops?”

Here you are comparing many valid answers and choosing the best one.

Important connection:
Many optimization problems can be rewritten as decision problems.
Example: instead of “What is the shortest route?” you ask, “Is there a route shorter than 50 miles?” That shift matters when we talk about efficiency.

2. What Algorithmic Efficiency Means

An algorithm’s efficiency is an estimate of how many computational resources it uses.

Resources usually mean:

• Time (how long it runs)
• Sometimes memory (how much storage it uses)

Efficiency depends on input size.

• Small list → fewer steps
• Large list → more steps

We describe efficiency as a function of input size. You are not measuring seconds. You are describing how the number of steps grows as the input grows.

You do not need formal Big-O notation for AP CSP. But you absolutely need to understand growth behavior.

Two correct algorithms for the same problem can have very different efficiencies. One might check every possible solution. Another might eliminate bad options early. Both give correct answers. One scales much better.

3. How to Estimate Efficiency

On the AP exam, you estimate efficiency informally by reasoning about how many times code runs.

Counting Executions

You look at how many times a statement (or group of statements) executes.

If a loop runs once for every item in a list of size n, then it runs about n times.

FOR EACH item IN aList
{
   DISPLAY(item)
}

If aList has 100 items, the display statement runs 100 times.

Now look at nested loops:

FOR EACH item1 IN aList
{
   FOR EACH item2 IN aList
   {
      DISPLAY(item1)
      DISPLAY(item2)
   }
}

If aList has n items:

• Outer loop runs n times.
• Inner loop runs n times for each outer loop.
• Total ≈ n × n times.

That grows much faster as n increases.

You don’t need formulas. You just need to recognize patterns:

• One loop → grows with input.
• Nested loops → grows much faster.
• More repetition → less efficient at large scale.

4. Reasonable vs Unreasonable Running Time

Algorithms are grouped by how their running time grows.

Reasonable Time

Algorithms with polynomial growth or slower are considered reasonable.

Examples of growth:

• Constant
• Linear
• Quadratic
• Cubic

These remain practical as input increases.

Unreasonable Time

Algorithms with exponential or factorial growth are considered unreasonable.

These explode extremely fast.

The graph below compares common Big‑O growth rates as the number of elements increases.

Common Big‑O growth rates compared

Notice how O(1), O(log n), and O(n) stay relatively low as input grows. Polynomial functions like O(n²) increase faster but are still considered reasonable for many problems.

Exponential O(2ⁿ) and factorial O(n!) shoot upward very quickly. Adding just a few more inputs can make runtime skyrocket. A problem might be solvable in theory, but not in any practical amount of time.

This connects to a core idea for the exam: even when a computer can solve a problem, it may not be able to solve it in a reasonable amount of time.

5. When and Why Heuristics Are Used

Some problems have no known efficient algorithm.

In those cases, we use a heuristic.

A heuristic:

• Produces a solution that is not guaranteed to be optimal
• Often finds a solution that is “good enough”
• Runs much faster than an exact method

Example scenario:
If finding the absolute shortest route between 20 cities takes exponential time, a heuristic might quickly find a route that is close to shortest.

On the exam, if you see:

• A guaranteed optimal algorithm that takes unreasonable time
• A faster method that gives near-optimal results

You should recognize the faster one as a heuristic.

You are trading perfection for practicality.