StudyBrixFree worksheets, study guides and courses

Computer science · University

Algorithms, invariants and asymptotic costs

An algorithm should have a stated input contract, output goal and termination argument. A loop invariant describes what remains true at a defined point in each iteration.

Make a worksheet

Prerequisites

Relevant school subject foundations and careful reasoning.

Study notes

Correctness

An algorithm should have a stated input contract, output goal and termination argument. A loop invariant describes what remains true at a defined point in each iteration.

Growth

Big-O describes asymptotic upper growth bounds, not exact seconds on every machine. State the operation and input size being counted.

Search

Binary search requires a sorted sequence and consistent ordering. It reduces the remaining interval at each step.

Testing

Edge cases such as empty inputs, duplicate values and boundaries complement proofs; passing examples alone does not prove correctness.

Worked examples

Which input condition does ordinary binary search require?

Ordering enables discarding half the interval safely.

A sorted sequence under the comparison rule

A procedure performs exactly 3n+2 operations in a stated model. Find the count for n=10.

3×10+2=32.

32

Check your understanding

  1. What does a loop invariant describe?

    1. A condition preserved at a specified loop point
    2. The processor brand
    3. A random input guess
    4. Only the final printed word

  2. An interval of 64 candidates is halved exactly three times. How many remain?

  3. Why does O(n) not tell us an exact runtime in seconds?

  4. Which is an important test input for a search function?

    1. Only a screenshot
    2. Only a large output font
    3. An empty collection
    4. Only one usual successful case

Answers and marking guidance

Answers and marking notes
  1. A condition preserved at a specified loop point

    Initialization, preservation and termination connect the invariant to correctness.

  2. 8

    64/2³=8.

  3. It describes asymptotic growth under a cost model, while constants, hardware, implementation and input details affect wall-clock time.

    Credit growth versus measured runtime.

  4. An empty collection

    Boundary cases can reveal indexing and termination bugs.

Further reading and review references

These are reference links, not copied exercises, institutional endorsement or proof of independent review.

AI-assisted preview; independent educational review required. Level labels describe prerequisites, not accreditation or official curriculum alignment.