Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 55 ยท Logic and Programs

Algorithms and Problem Solving

Learn what an algorithm is, how to express one with pseudocode and flowcharts, how to check it is correct, and why efficiency matters, with step-counting examples.

An algorithm is a finite, precise list of steps that solves a problem. A recipe is an algorithm for dinner, directions are an algorithm for getting somewhere, and the method you learned for long division is an algorithm for dividing. What makes it an algorithm rather than a vague suggestion is that every step is clear enough to follow without guessing, and that it eventually stops with an answer.

Computers are good at following algorithms very quickly, but they cannot invent them. Part of learning to program is learning to break a problem into steps. This lesson shows how to describe algorithms, how to check them, and why two correct algorithms can differ enormously in speed. It follows Programming Languages, Compilers and Interpreters.

What makes a good algorithm

A useful algorithm has these properties:

  • Input: zero or more values it starts with.
  • Output: at least one result.
  • Definiteness: each step is unambiguous. "Add some salt" is not a step; "add 5 grams of salt" is.
  • Finiteness: it ends after a limited number of steps.
  • Correctness: it gives the right answer for every valid input, not just the ones you tried.
  • Efficiency: it does not waste time or memory.

Solving a problem step by step

A reliable way to approach any problem:

  1. Understand it. What is the input? What exactly should the output be? Work a small example by hand.
  2. Plan. Break the problem into smaller problems, and look for a pattern you already know (searching, sorting, counting, repeating).
  3. Write the steps in pseudocode or a flowchart.
  4. Test with ordinary cases and with edge cases.
  5. Improve if it is too slow or too complicated.

Skipping straight to code is the most common beginner mistake. If you cannot do it by hand on paper, you cannot yet tell a computer how.

Pseudocode

Pseudocode is a plain-language description of an algorithm that follows the logic of programming but ignores the strict spelling rules of any language. There is no official standard: the goal is that a person can read it and implement it in any language. Here is an algorithm to find the largest number in a list:

TEXT
FIND-LARGEST(list)
  set largest to the first item of list
  for each remaining item in list
    if item is greater than largest
      set largest to item
  return largest

It uses the three building blocks every algorithm is made of: sequence (steps in order), selection (an if choosing between paths) and iteration (a loop repeating steps).

Flowcharts

A flowchart draws the same idea as boxes and arrows. Diamonds are decisions, rectangles are actions and arrows show the order. This one is Euclid's method for the greatest common divisor, one of the oldest algorithms still in use.

flowchart TD
  A["Start with numbers a and b"] --> B{"Is b equal to 0?"}
  B -->|"yes"| C["Answer is a"]
  B -->|"no"| D["Replace a with b,<br/>and b with the remainder of a / b"]
  D --> B

Euclid's algorithm: keep replacing the pair until the second number becomes zero.

Now turn it into something that runs. The trace prints each round so you can see the numbers shrink, and the tests check ordinary cases and edge cases.

JS Euclid's algorithm with a trace and tests

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Is it correct?

Correctness is more than "it worked once". Ways to gain confidence:

  • Trace by hand a small input and compare it with the program.
  • Test edge cases: an empty list, a single item, duplicates, zero, negative numbers, very large values.
  • State an invariant: something that stays true each time round the loop. In FIND-LARGEST, "largest is the biggest item seen so far" is true after every step, and when the loop ends, "so far" covers the whole list.
  • Ask what could go wrong: what happens with an empty list? The pseudocode above would fail, so a careful version either rejects it or defines a result for it.

Testing can show that a bug exists but never proves that none does; reasoning about invariants complements it.

Why efficiency matters

Two algorithms can both be correct yet differ by a factor of a million. A classic example is searching a sorted list of numbers.

  • Linear search checks items one at a time from the start. In the worst case it looks at every item.
  • Binary search looks at the middle item: if it is too big, the target must be in the left half; if too small, in the right half. It discards half of the remaining items with every check. It only works because the list is sorted.

The stand-in below counts comparisons in the worst case instead of measuring time (timing varies from machine to machine, counts do not).

JS Counting steps: linear versus binary search

Press Run (or Ctrl + Enter) to see the console output here.

No output.

For a million items, linear search needs up to a million checks while binary search needs about twenty. Doubling the size of the list adds just one more step for binary search, but doubles the work for linear search. That is what people mean by how an algorithm grows with input size.

A first look at growth

Computer scientists describe growth with Big O notation, ignoring small details to show the overall trend:

Growth Name Example Doubling the input...
O(1) constant read item number 5 of a list does not change the work
O(log n) logarithmic binary search adds one step
O(n) linear find the maximum doubles the work
O(nยฒ) quadratic compare every pair quadruples the work

At small sizes you will not notice any difference. At large sizes the gap decides whether a program finishes in a blink, in an hour or never. The full story is for a later course, but the habit begins here: when you design a solution, ask how its work grows as the input grows.

JS How fast does work grow?

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Algorithms are also the topic of whole courses, see for example the Data Structures and Algorithms tutorial on this site at /dsa, where each idea here is developed in depth.

When you are stuck, solve a smaller version of the problem by hand, write down exactly what you did, and then turn those notes into steps. Most algorithms are just careful notes about how a person would do the job.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which is NOT a required property of an algorithm?

    Algorithms are independent of any language. Pseudocode, flowcharts or plain words can describe them.
  2. 2. What are the three basic building blocks of algorithms?

    Steps in order, decisions with if, and loops repeating steps combine to express any algorithm.
  3. 3. Binary search needs the list to be...

    Binary search discards half of the items using order, so an unsorted list breaks it.
  4. 4. About how many comparisons does binary search need, at most, for 1,000,000 sorted items?

    Each check halves the remaining range, and log2 of a million is just under 20, so about 20 checks.
  5. 5. If an O(n squared) algorithm takes 1 second for 1,000 items, roughly how long for 2,000?

    Doubling the input multiplies the work by four for quadratic growth.

Summary

  • An algorithm is a finite, precise, step-by-step method that produces a result.
  • Every algorithm is built from sequence, selection and iteration.
  • Pseudocode and flowcharts describe algorithms without the rules of a language.
  • Check correctness by tracing, testing edge cases and stating invariants.
  • Count steps, not seconds, to compare algorithms fairly; binary search needs about log2 n steps against n for linear search.
  • Big O notation summarises how the work grows with the input size.

You now know how computers calculate and how programs are written and translated. Next we study the software that runs everything else: What an Operating System Does.