Understand how growing inputs change the work and memory AI needs.
An algorithm is a set of instructions for solving a problem. Computational complexity describes how its work or memory needs grow as the input grows. Number precision means how much detail a stored number keeps. You will count simple steps, estimate AI costs, and explore quantization, which stores a model's learned numbers in fewer bits.
Free preview — no account needed. This is the Basic level of a Mathematical Foundations lesson from the AI Professional Series. The Intermediate and Advanced levels, with 20 more practice exercises and a Concept Quiz, are part of AI Professional. Optional practice only: it does not affect course totals, exams or certificates.
See AI Professional plansThis is the Basic level. There are 10 practice exercises, each with a hint and a full worked solution.
Start here if counting program steps is new to you. Compare common patterns and learn why input size matters.
Input size means how much data a program receives. We often call it n. An operation is one small action we choose to count, such as adding a number. A step count is useful only when we say which actions we count.
In everyday words: To compare shopping trips, count the items collected rather than every movement of your feet.
additions = nRead it as: The number of additions equals the number of input items.
Worked example: Start a total at zero and add each of 5 numbers. How many additions occur?
Answer: There are 5 additions; initialization and loop control are not included.
values = [2, 4, 6, 8, 10]
total = 0
additions = 0
for value in values:
total += value
additions += 1
print(total, additions)Why it matters in AI: AI programs repeatedly process lists of examples or numbers. A clear counting rule helps you compare approaches fairly.
Big-O describes an upper bound on how work grows for large inputs. It hides fixed multipliers and smaller extra terms. O(1), called constant time, means the work stays bounded as input size grows. It does not mean exactly one operation.
In everyday words: Reading a labeled locker number takes similar work whether the building has 20 lockers or 200.
T(n) = 3; T(n) is O(1)Read it as: The counted work is three steps for every input size, so it has constant growth.
Worked example: A routine always performs 3 counted actions. Compare inputs of 10 and 1000 items.
Answer: Both inputs require 3 counted actions, so this work is O(1).
Why it matters in AI: Reading a stored setting by an array position can be constant-time work. Big-O alone does not tell you its measured speed.
Linear growth means work rises in direct proportion to input size. A loop that visits every item once has linear work, written O(n). Quadratic growth means work rises with the square of input size. Two full loops, one inside the other, do n × n visits when both cover n items.
In everyday words: Greeting each guest once is linear work. Asking every guest to address every guest, including themselves, is quadratic work.
one full loop: n visits; two full nested loops: n² visitsRead it as: One full loop makes n visits; two full nested loops make n squared visits.
Worked example: Compare one full loop and two full nested loops for 4 items, then 8 items.
Answer: The counts change from 4 to 8 for linear work and from 16 to 64 for quadratic work.
n = 4
visits = 0
for i in range(n):
for j in range(n):
visits += 1
print(visits)Why it matters in AI: Comparing every AI data item with every other item can create quadratic work. Larger datasets can therefore become expensive quickly.
A search looks for a target value. Linear search checks items one at a time. Binary search uses sorted data, meaning values are in order, and discards about half the remaining choices after each check. Binary search also needs quick access to the middle item; sorting beforehand has its own cost.
In everyday words: You might inspect every loose receipt, but you can repeatedly split a stack of receipts already ordered by date.
linear search worst case: n checks; binary search worst case: floor(log2 n) + 1 checks for n ≥ 1Read it as: Linear search may check all n items. Binary search needs at most one more than the whole-number part of the base-two logarithm of n; that logarithm measures repeated halving.
Worked example: Search for 15 in the sorted array [1, 3, 5, 7, 9, 11, 13, 15]. Use the lower middle position when needed.
Answer: Linear search uses 8 item checks; this binary search uses 4.
Why it matters in AI: Ordered indexes can make repeated lookups much cheaper. The cost of creating and maintaining the index still matters.
Try each one on paper first. Use the hint if you get stuck, then check the full solution.
Exercise 1. A loop adds each of 6 numbers to a total. Count only those additions. How many occur?
Exercise 2. A routine always makes 4 checks, whether it receives 5 or 500 items. What is its Big-O growth?
Exercise 3. A full loop visits 12 items once each. How many visits occur, and what is its growth class?
Exercise 4. A full loop grows from 9 items to 27 items. By what factor does its visit count grow?
Exercise 5. Two full nested loops each visit 5 items. How many times does the inner action run?
Exercise 6. Two full nested loops grow from 3 items each to 6 items each. Compare their action counts.
Exercise 7. A routine makes 2 × n + 3 counted steps. Find the count for n = 10 and its usual simplest Big-O description.
Exercise 8. Linear search checks a list of 20 items for a target that is absent. How many item checks are needed?
Exercise 9. Binary search looks for 14 in [2, 4, 6, 8, 10, 12, 14]. How many item checks occur?
Exercise 10. For n = 100, routine A makes 5 × n steps and routine B makes n² steps. Which uses fewer steps, and by what factor?