Home / C++ / Complexity, testing, and C++ projects

C++ PROGRAMMING · 25 MIN STUDY

Complexity, testing, and C++ projects

Analyze algorithm growth, plan small projects, test edge cases, and improve code through refactoring.

Learning objectives

  • Describe time and space complexity using Big O.
  • Estimate costs of common vector and map operations.
  • Plan a program from requirements into functions and data types.
  • Test normal, boundary, and invalid cases.

Prerequisites: functions, loops, vectors, and basic STL containers. Review Functions, Loops, std::vector, and STL containers first.

Why complexity matters

Two correct programs can behave very differently as input grows. Time complexity describes how an algorithm's work grows with input size. Space complexity describes how its additional memory use grows. Big O describes an upper growth rate, not a stopwatch prediction.

GrowthExample intuition
O(1)Access a vector element by index
O(log n)Binary search on sorted random-access data
O(n)Scan all elements once
O(n log n)Comparison sorting such as std::sort
O(n²)Compare every pair with nested loops

Analyze a loop

for (int i = 0; i < n; ++i) {
    std::cout << i << '\n';
}

The loop body runs n times, so its time growth is O(n). The loop uses a fixed number of extra variables, so its auxiliary space is O(1).

Plan before coding

  1. Write down what the program must do (functional requirements).
  2. Identify the input, output, and invalid cases.
  3. Choose data structures based on required operations.
  4. Break the work into functions with clear responsibilities.
  5. Implement one small part and test it before adding more.
  6. Review names, duplication, error handling, and complexity.

Project 1: unit converter

Requirements: accept a value and a unit choice, convert between Celsius and Fahrenheit, reject unsupported choices, and print a clearly labelled result. Keep conversion formulas in separate functions and test known values such as 0°C and 100°C.

Project 2: student record manager

Requirements: store student records in a vector of structures, add and search records, calculate an average, and save/load records from a text file. Validate identifiers and numeric inputs. Separate data operations from console prompts.

Project 3: inventory manager

Requirements: model products with a class or structure, store them in an associative container keyed by product ID, update stock, search records, and report low stock. Consider how the chosen container affects lookup and ordering.

Testing strategy

  • Normal case: common valid input.
  • Boundary case: empty list, zero, one element, minimum/maximum supported value.
  • Invalid case: malformed input, missing file, unknown ID.
  • Regression case: rerun previous tests after a change.

Common mistakes

  • Writing the whole project in main.
  • Choosing a data structure without considering its operations.
  • Testing only one successful input.
  • Optimizing before measuring or understanding the complexity.
  • Ignoring compiler warnings and error paths.

Practice

  1. Analyze the time complexity of a nested loop that compares every pair of n values.
  2. Write a requirements list for a library book manager.
  3. Choose a container for unique sorted IDs and explain why.
  4. Create tests for empty, single-element, and duplicate inputs for a search function.

Check your understanding

Does O(n) mean the program always takes n seconds?

Answer: No. It describes how work grows with input size, not a fixed runtime measurement.

Practice solutions

Show reasoned solutions
  1. If the outer loop visits all n values and the inner loop also visits all n values, the body runs n × n times: O(n²). If it compares only distinct pairs with j = i + 1, it runs n(n - 1) / 2 times, which is still O(n²).
  2. A useful library-manager requirements list includes adding a book, assigning a unique ID, searching by ID/title, marking a book as borrowed/returned, listing available books, saving/loading records, and reporting missing or invalid input. State how duplicate IDs and missing records are handled.
  3. Use std::set<int> when IDs must be unique and iterated in sorted order. Its search, insertion, and removal are O(log n).
  4. Test an empty collection; a one-element collection with match and no match; a match at the first and last positions; absent values; duplicates; and sorted/reverse-sorted data if the search algorithm depends on ordering. Define the expected behavior for each case.

Summary

Use complexity to reason about growth, choose containers based on operations, plan projects from requirements, and test edge cases. A complete program is more than code that compiles: it must behave correctly and be maintainable.

References