15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A time complexity chart ranks growth classes from slowest-growing to fastest-growing: O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3). At n = 8 the operation counts are 1, 3, 8, 24 and 64 for the first five. Halving gives log n, one visit per item gives n, and a loop over all pairs gives n^2.
| O(1), fixed work | 1 at n = 8, does not depend on n |
|---|---|
| O(log n), repeated halving | 3 at n = 8: 8, 4, 2, 1 |
| O(n), one visit per item | 8 at n = 8 |
| O(n log n), n rounds of halving | 8 x 3 = 24 at n = 8 |
| O(n^2), every ordered pair | 8 x 8 = 64; three nested choices give O(n^3) |
| Two scans in a row | n + n = 2n, still O(n) |
The lesson uses asymptotic notation. An expression such as describes how a work count grows as the input size grows.
Before assigning a class, define what means.
Define the input size and counted work before assigning a class.
The classes in this lesson, ordered by their representative growth rates for sufficiently large , are:
The lesson uses the cubic class to show growth beyond quadratic.
The standard growth forms and their analysis are consistent with these course references:
Use one input size throughout:
Compare these operation-count expressions:
| Expression | Value at | Class |
|---|---|---|
One input-size value illustrates an expression. An asymptotic class describes growth as changes.
Start with the five expressions at .
At n = 8 the five classes cost 1, 3, 8, 24 and 64 operations: O(1), O(log n), O(n), O(n log n) and O(n²). The gap widens fast as n grows.
| State | Calculation | Result |
|---|---|---|
| State 0 | , so | |
| State 1 | halvings, so | |
| State 2 | , so | |
| State 3 | , so | |
| State 4 | , so |
A constant-work operation does not depend on the number of input items.
A representative shape is one fixed action:
1read one known positionWhether there are 8 items or 8,000 items, the model count remains 1.
For logarithmic work, begin at 8 and halve the remaining size.
| Step | Remaining size |
|---|---|
| 0 | 8 |
| 1 | 4 |
| 2 | 2 |
| 3 | 1 |
There are three halving steps:
A representative shape is:
1while remaining size is greater than 1:
2 halve the remaining sizeIf work happens once for each of 8 items:
A representative shape is one loop that visits every item once:
1for each item:
2 perform one operationThe model count is , so the class is .
Combine the two counts.
There are 8 rounds. Each round has 3 halving levels.
The expression means multiplication.
A representative shape is:
1repeat once for each item:
2 repeatedly halve a remaining sizeThe shape has rounds of logarithmic work, giving .
For every first item, pair it with every second item.
A representative shape is two nested loops, each visiting items:
1for each first item:
2 for each second item:
3 process the ordered pairThere are choices for the first item times choices for the second, giving .
Three nested choices produce:
The class is .
Focus on the halving process. The states are:
The fact that remains true is:
After halving steps, the remaining size is . The process stops once this quantity reaches 1.
The halving helper uses this loop invariant.
At termination:
For :
So:
In general, for this repeated-halving model:
The base does not change the asymptotic class. For positive bases other than 1:
The denominator is a constant. Changing from to changes the count by a constant factor and retains the label.
The practice task computes exact model values for five modes. It does not perform all the modeled work. For example, allPairs returns ; it does not actually visit every pair.
Define the modes:
| Mode | Exact model value |
|---|---|
constant | |
halve | number of halving steps, , for positive |
scan | |
scanThenHalve | , for positive |
allPairs |
To compute the halving count:
remaining to n.steps to 0.remaining > 1, replace it with floor(remaining / 2).steps once per halving.steps.For , the helper produces 3. Then:
halve returns 3.scanThenHalve returns .Boundary decisions:
Input: n, a nonnegative integer; mode, one of constant, halve, scan, scanThenHalve, or allPairs.
Return value: The exact operation-count model for the requested mode.
Mutation behavior: Neither function changes n or mode. The helper changes only its local variables.
Helper contract: floorLog2Steps(n) requires n > 0 and returns the number of times integer halving can occur before the remaining value reaches 1.
1 1 function floorLog2Steps(n):
2 2 require n > 0
3 3 remaining ← n
4 4 steps ← 0
5 5 while remaining > 1:
6 6 remaining ← floor(remaining / 2)
7 7 steps ← steps + 1
8 8 return steps
9
10 9 function classifyCount(n, mode):
1110 require n ≥ 0
1211
1312 if mode = "constant":
1413 return 1
1514
1615 if mode = "scan":
1716 return n
1817
1918 if mode = "allPairs":
2019 return n × n
2120
2221 if mode = "halve" or mode = "scanThenHalve":
2322 require n > 0
2423 levels ← floorLog2Steps(n)
2524
2625 if mode = "halve":
2726 return levels
2827 else:
2928 return n × levels
3029
3130 error "unknown mode"Use the original input size, , for every mode.
classifyCount(8, "constant")| Line | State change or decision |
|---|---|
| 10 | 8 ≥ 0, so the input is valid. |
| 12 | Mode is "constant". |
| 13 | Return 1. |
The result matches State 0:
classifyCount(8, "halve")| Line | State change or decision |
|---|---|
| 10 | 8 ≥ 0, so the input is valid. |
| 12 | Mode is not "constant". |
| 15 | Mode is not "scan". |
| 18 | Mode is not "allPairs". |
| 21 | Mode is "halve", so enter this branch. |
| 22 | 8 > 0, so the logarithmic model is valid. |
| 23 | Call floorLog2Steps(8). |
Now follow the helper line by line.
| Helper line | remaining | steps | Explanation |
|---|---|---|---|
| 2 | — | — | 8 > 0, so the helper precondition holds. |
| 3 | 8 | — | Set remaining ← 8. |
| 4 | 8 | 0 | Set steps ← 0. |
| 5 | 8 | 0 | 8 > 1, enter the loop. |
| 6 | 4 | 0 | floor(8 / 2) = 4. |
| 7 | 4 | 1 | Count the first halving. |
| 5 | 4 | 1 | 4 > 1, enter the loop. |
| 6 | 2 | 1 | floor(4 / 2) = 2. |
| 7 | 2 | 2 | Count the second halving. |
| 5 | 2 | 2 | 2 > 1, enter the loop. |
| 6 | 1 | 2 | floor(2 / 2) = 1. |
| 7 | 1 | 3 | Count the third halving. |
| 5 | 1 | 3 | 1 > 1 is false; exit the loop. |
| 8 | — | — | Return 3. |
Back in classifyCount:
| Line | State change or decision |
|---|---|
| 23 | Set levels ← 3. |
| 25 | Mode is "halve". |
| 26 | Return 3. |
The result matches State 1:
classifyCount(8, "scan")| Line | State change or decision |
|---|---|
| 10 | 8 ≥ 0, so the input is valid. |
| 12 | Mode is not "constant". |
| 15 | Mode is "scan". |
| 16 | Return 8. |
The result matches State 2:
classifyCount(8, "scanThenHalve")| Line | State change or decision |
|---|---|
| 10 | 8 ≥ 0, so the input is valid. |
| 12 | Mode is not "constant". |
| 15 | Mode is not "scan". |
| 18 | Mode is not "allPairs". |
| 21 | Mode is "scanThenHalve", so enter this branch. |
| 22 | 8 > 0, so the logarithmic model is valid. |
| 23 | Call floorLog2Steps(8). |
| 2 | 8 > 0, so the helper precondition holds. |
| 3 | Set remaining ← 8. |
| 4 | Set steps ← 0. |
| 5 | 8 > 1, enter the loop. |
| 6 | Set remaining ← floor(8 / 2) = 4. |
| 7 | Set steps ← 1. |
| 5 | 4 > 1, enter the loop. |
| 6 | Set remaining ← floor(4 / 2) = 2. |
| 7 | Set steps ← 2. |
| 5 | 2 > 1, enter the loop. |
| 6 | Set remaining ← floor(2 / 2) = 1. |
| 7 | Set steps ← 3. |
| 5 | 1 > 1 is false; exit the loop. |
| 8 | Return 3. |
| 23 | Set levels ← 3. |
| 25 | Mode is not "halve", so use the else branch. |
| 28 | Return 8 × 3 = 24. |
The result matches State 3:
classifyCount(8, "allPairs")| Line | State change or decision |
|---|---|
| 10 | 8 ≥ 0, so the input is valid. |
| 12 | Mode is not "constant". |
| 15 | Mode is not "scan". |
| 18 | Mode is "allPairs". |
| 19 | Return 8 × 8 = 64. |
The result matches State 4:
We prove that floorLog2Steps(n) returns the number of integer-halving steps needed to reach 1 for every positive input in this model.
Initialization: Before the loop, line 3 sets:
Line 4 sets:
After zero halving steps, the remaining size is . The invariant holds.
Preservation: Assume the invariant holds at the start of an iteration: after steps halvings, remaining represents the input after that many halvings. Line 6 halves remaining. Line 7 increases steps by one. After the iteration, remaining represents one additional halving, so the invariant still holds.
Termination: The loop stops when remaining ≤ 1. Since positive integer halving does not produce a value below 1 while the loop condition is true, the stopping value is 1. By the invariant, steps is exactly the number of halving steps required to reach 1. Line 8 returns that value.
Each recognized mode returns its required model value directly:
"constant" returns 1 at line 13."scan" returns at line 16."allPairs" returns at line 19."halve" obtains the correct halving count from the proven helper and returns it at line 26."scanThenHalve" obtains the same correct count and multiplies it by at line 28.For logarithmic modes, line 22 rejects , where the logarithm model is undefined. For an unknown mode, line 30 reports an error rather than returning a value for a different mode.
For every valid input and supported mode, classifyCount returns the specified exact model value.
The returned value describes a model of another algorithm’s work. Derive each class from that modeled work.
| Modeled work | Count derivation | Class |
|---|---|---|
| Fixed work | The count does not depend on . | |
| Repeated halving | Solve , giving . | |
| One operation per item | There are item visits. | |
| rounds of halving work | rounds times work per round. | |
| Every ordered pair | first choices times second choices. | |
| Every ordered triple | . |
For the example :
come from the same derivations.
Two consecutive scans have time.
If each loop visits an eight-item array once:
For general :
Constant factors are ignored asymptotically, so the class is .
For the modeled algorithm shapes, auxiliary space depends on what the particular algorithm stores; the operation counts alone do not determine it.
For the provided classifyCount pseudocode:
floorLog2Steps stores remaining and steps.classifyCount stores levels only for logarithmic modes.So the classifier uses auxiliary space.
The classifier’s running time differs from the model value it returns:
constant, scan, and allPairs return after a fixed number of pseudocode steps.halve and scanThenHalve run the helper, which performs one iteration per halving level.Thus the classifier takes time in its logarithmic modes, even though scanThenHalve returns the model value .
Incorrect assumption:
1count ← n + log2(n)Exposing input:
Wrong result:
Correct calculation:
Juxtaposition means multiplication.
Incorrect assumption:
1levels ← n / 2Exposing input:
Wrong result:
Correct state sequence:
There are 3 halving steps, so:
Incorrect assumption:
1log2(n) and log10(n) need different asymptotic labelsExposing input: compare and
Wrong result: different Big-O classes.
Correction:
The factor is constant. Both are .
Incorrect assumption:
1for each item:
2 process item
3
4for each item:
5 process item
6
7therefore count = n × nExposing input: two loops, each visiting an eight-item array once.
Wrong count:
Correct count:
For general , the count is , which is . Counts multiply when one amount of work is performed inside each iteration of another amount of work.
Incorrect line:
1levels ← floorLog2Steps(n)without checking that n > 0.
Exposing input: , mode "halve".
Wrong state: The logarithmic model has no defined value because is undefined.
Correction: Check n > 0 before calling the helper, as line 22 does.
Implement:
1classifyCount(n, mode)Supported modes and required exact results are:
| Mode | Required result |
|---|---|
constant | |
halve | floor-log-base-2 step count for positive |
scan | |
scanThenHalve | times the floor-log-base-2 step count for positive |
allPairs |
The executable tests use:
Your implementation contract must preserve these boundaries:
halve and scanThenHalve, accept only positive .scanThenHalve must return .1def floor_log2_steps(n):
2 assert n > 0
3 remaining, steps = n, 0
4 while remaining > 1:
5 remaining //= 2
6 steps += 1
7 return steps
8
9def classify_count(n, mode):
10 if mode == "constant":
11 return 1
12 if mode == "scan":
13 return n
14 if mode == "allPairs":
15 return n * n
16 if mode in ("halve", "scanThenHalve"):
17 if n <= 0:
18 raise ValueError("logarithm undefined for n = 0")
19 levels = floor_log2_steps(n)
20 return levels if mode == "halve" else n * levels
21 raise ValueError("unknown mode")
22
23for mode in ["constant", "halve", "scan", "scanThenHalve", "allPairs"]:
24 print(f"{mode}(8) = {classify_count(8, mode)}")
25print(f"halve(16) = {classify_count(16, 'halve')}")
26print(f"halve(1) = {classify_count(1, 'halve')}")1public class Main {
2 static int floorLog2Steps(int n) {
3 int remaining = n, steps = 0;
4 while (remaining > 1) {
5 remaining /= 2;
6 steps++;
7 }
8 return steps;
9 }
10
11 static int classifyCount(int n, String mode) {
12 if (mode.equals("constant")) return 1;
13 if (mode.equals("scan")) return n;
14 if (mode.equals("allPairs")) return n * n;
15 if (mode.equals("halve") || mode.equals("scanThenHalve")) {
16 if (n <= 0) throw new IllegalArgumentException("logarithm undefined for n = 0");
17 int levels = floorLog2Steps(n);
18 return mode.equals("halve") ? levels : n * levels;
19 }
20 throw new IllegalArgumentException("unknown mode");
21 }
22
23 public static void main(String[] args) {
24 String[] modes = {"constant", "halve", "scan", "scanThenHalve", "allPairs"};
25 for (String mode : modes) {
26 System.out.println(mode + "(8) = " + classifyCount(8, mode));
27 }
28 System.out.println("halve(16) = " + classifyCount(16, "halve"));
29 System.out.println("halve(1) = " + classifyCount(1, "halve"));
30 }
31}1#include <iostream>
2#include <stdexcept>
3#include <string>
4#include <vector>
5using namespace std;
6
7int floorLog2Steps(int n) {
8 int remaining = n, steps = 0;
9 while (remaining > 1) {
10 remaining /= 2;
11 steps++;
12 }
13 return steps;
14}
15
16int classifyCount(int n, const string& mode) {
17 if (mode == "constant") return 1;
18 if (mode == "scan") return n;
19 if (mode == "allPairs") return n * n;
20 if (mode == "halve" || mode == "scanThenHalve") {
21 if (n <= 0) throw invalid_argument("logarithm undefined for n = 0");
22 int levels = floorLog2Steps(n);
23 return mode == "halve" ? levels : n * levels;
24 }
25 throw invalid_argument("unknown mode");
26}
27
28int main() {
29 vector<string> modes = {"constant", "halve", "scan", "scanThenHalve", "allPairs"};
30 for (const string& mode : modes) {
31 cout << mode << "(8) = " << classifyCount(8, mode) << endl;
32 }
33 cout << "halve(16) = " << classifyCount(16, "halve") << endl;
34 cout << "halve(1) = " << classifyCount(1, "halve") << endl;
35}1function floorLog2Steps(n) {
2 let remaining = n;
3 let steps = 0;
4 while (remaining > 1) {
5 remaining = Math.floor(remaining / 2);
6 steps++;
7 }
8 return steps;
9}
10
11function classifyCount(n, mode) {
12 if (mode === 'constant') return 1;
13 if (mode === 'scan') return n;
14 if (mode === 'allPairs') return n * n;
15 if (mode === 'halve' || mode === 'scanThenHalve') {
16 if (n <= 0) throw new Error('logarithm undefined for n = 0');
17 const levels = floorLog2Steps(n);
18 return mode === 'halve' ? levels : n * levels;
19 }
20 throw new Error('unknown mode');
21}
22
23for (const mode of ['constant', 'halve', 'scan', 'scanThenHalve', 'allPairs']) {
24 console.log(`${mode}(8) = ${classifyCount(8, mode)}`);
25}
26console.log(`halve(16) = ${classifyCount(16, 'halve')}`);
27console.log(`halve(1) = ${classifyCount(1, 'halve')}`);From slowest to fastest growth: O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3). Exponential and factorial classes grow faster than all of them, though this lesson stops at cubic.
No. The two terms multiply. At n = 8, n + log n would give 8 + 3 = 11, while n log n is 8 x 3 = 24: n rounds, each with 3 halving levels.
No. Halving 8 gives 8, 4, 2, 1, which is 3 steps, so log2(8) = 3. The value n / 2 would be 4. Doubling n to 16 adds only one step.
No. log10 n = log2 n / log2 10, and the divisor is a constant. Every log base lands in the same O(log n) class.
No. Sequential work adds: two loops over 8 items do 8 + 8 = 16 operations, which is 2n, so O(n). Counts multiply only when one loop runs inside the other.