# 2.1 Algorithms & Their Properties

> An algorithm is a finite, unambiguous sequence of steps that solves a problem. Learn the 11 properties every correct algorithm must have.

Chapter: Algorithm & Algorithm Analysis · ~30 min · easy
URL: https://dsa.fetehadin.com/learn/algorithm-properties

## Mental model

An **algorithm** is a recipe precise enough for a machine: *a finite sequence of well-defined steps that takes some input and produces the correct output.*

A cooking recipe that says "bake until it looks good" is fine for humans, but it isn't an algorithm. A computer can't judge "looks good". Every step must be exact.

### The 11 properties

| Property | Meaning |
|---|---|
| **Finiteness** | It must stop after a finite number of steps. |
| **Definiteness** | Every step is clear and has exactly one meaning. |
| **Sequence** | Steps run in a defined order; each step has a unique next step. |
| **Feasibility** | Every step can actually be carried out with the available resources. |
| **Correctness** | It produces the right output for every valid input. |
| **Language independence** | The steps can be written in any language (C++, Python, pseudocode). |
| **Completeness** | It solves the whole problem, including edge cases. |
| **Effectiveness** | Each step is basic enough to do exactly, in finite time, even by hand. |
| **Efficiency** | It uses as little time and memory as possible. |
| **Generality** | It works for a whole class of problems, not one fixed input. |
| **Input / Output** | Zero or more inputs; at least one output. |

> Memory trick: **"Fine Dogs Sit, Feel Calm, Learn Commands; Every Excited Good I/O."** Silly, but it sticks.

### Algorithm vs program

A **program** is an algorithm written in a specific language and run on a machine. A program may run forever (a web server); an algorithm must finish.

## C++ code: find-max.cpp

```cpp
#include <iostream>
using namespace std;

// Input: an array and its size. Output: the largest value.
// Finite (n-1 comparisons), definite, effective, general, correct.
int findMax(const int a[], int n) {
    int max = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] > max)
            max = a[i];
    return max;
}

int main() {
    int a[] = {14, 3, 27, 9, 31, 8};
    int b[] = {-5, -2, -9};
    cout << "max of a = " << findMax(a, 6) << "\n";
    cout << "max of b = " << findMax(b, 3) << "\n";
}
```

Expected output:

```text
max of a = 31
max of b = -2
```

## Complexity

| Case | Cost |
| --- | --- |
| findMax: comparisons | exactly n − 1 |
| findMax: time | O(n), and best = worst |

Space: O(1)

Efficiency is one of the 11 properties. Chapter 2 is about measuring it precisely.

## Videos

- [Introduction to Algorithms](https://youtu.be/0IAPZzGSbME) (Abdul Bari): Abdul Bari covers what an algorithm is, its characteristics and how it differs from a program.

## Exam lens

Likely questions:

- Define algorithm. List and explain any five properties of an algorithm.
- What is the difference between finiteness and effectiveness?
- Why must an algorithm be language independent?
- Give an example of a set of steps that is NOT an algorithm and say which property it breaks.

Common mistakes:

- Confusing **definiteness** (each step has one clear meaning) with **finiteness** (the algorithm stops).
- Saying an algorithm needs at least one input. It needs **zero or more** inputs but **at least one** output.
- Treating "a program" and "an algorithm" as the same. A program may run forever (an OS); an algorithm must terminate.

## Quick check

1. "Add a pinch of salt" breaks which property?
   A. Finiteness
   B. Definiteness
   C. Generality
   D. Sequence
   Answer: B. "A pinch" can mean different amounts to different people. Each step must have exactly one meaning.

2. An algorithm must produce…
   A. zero or more outputs
   B. at least one output
   C. exactly one input
   D. at least one input
   Answer: B. Zero or more inputs, but at least one output. Otherwise it achieved nothing.

3. `while (true) { }` violates which property?
   A. Finiteness
   B. Feasibility
   C. Language independence
   D. Input
   Answer: A. It never terminates.

4. "Works for any array size, not just 5 items" describes…
   A. Correctness
   B. Generality
   C. Effectiveness
   D. Completeness
   Answer: B. A general algorithm solves every instance of the problem, not one special case.

## Practice

**Trace by hand.** Here is a "recipe": (1) pick a random number, (2) if it is the answer, stop; otherwise go to (1). Which properties does it break?

Solution:

- **Finiteness**: it may never stop.
- **Definiteness**: "pick a random number" is not one exact action.
- **Efficiency**: there is no bound on the number of steps.


**Implement it.** Write `findMin` and a `main()` that tests it on an array of negative numbers. Then write which property your test checks.

Hint: Start with `min = a[0]`, not `min = 0`. With `0` the algorithm is incorrect for all-positive arrays. That's the *correctness* property.

**Problems:**

- [Find Greatest Common Divisor of Array](https://leetcode.com/problems/find-greatest-common-divisor-of-array/) (easy). Hint: Find min and max in one pass, then apply Euclid's algorithm (a classic finite, definite algorithm).
- [Find the Highest Altitude](https://leetcode.com/problems/find-the-highest-altitude/) (easy). Hint: A running sum and a running max. Write the steps in plain English first, then code.

## Mastery checklist

- [ ] I can define an algorithm.
- [ ] I can list and explain the 11 properties.
- [ ] I can say which property a broken "algorithm" violates.
- [ ] I can explain the difference between an algorithm and a program.