15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Asymptotic notation labels how an operation count grows as the input size n increases, keeping only the growth class. Big O is an upper bound, Omega is a lower bound, and Theta means both hold. For T(n) = 3n + 2 and n >= 1, 3n <= T(n) <= 5n, so T(n) is Theta(n).
| Exact count | T(n) = 3n + 2 under a stated model; T(3) = 11 |
|---|---|
| Big O upper bound | 3n + 2 <= 5n for n >= 1, so O(n) |
| Big Omega lower bound | 3n + 2 >= 3n for n >= 1, so Omega(n) |
| Big Theta | Both bounds hold, so Theta(n) |
| Dominant term | n^2 + n + 2 and 100n + n^2 are both Theta(n^2) |
| Constant function | T(n) = 7 is Theta(1), not Theta(n) |
Assume you can describe an algorithm’s time and auxiliary-space cost as a function of input size .
Here, the input size is the number of items:
An exact operation count keeps the details of a chosen counting model. An asymptotic classification describes how that count grows as increases.
For example:
is an exact count under one stated model. Its asymptotic classification is:
Exact counts and asymptotic classifications describe different parts of the analysis.
The lesson uses standard definitions of asymptotic upper, lower, and tight bounds. It moves from a concrete operation count to its growth label.
Consider a scan-and-print algorithm on this input:
1items = [4, 1, 7]
2index 0 1 2For n ≥ 1, 3n ≤ 3n + 2 ≤ 5n. The exact count T(n) = 3n + 2 stays between two straight lines, so it grows linearly: Θ(n). At n = 3 the count is 11.
There are three items, so:
Use this exact cost model:
That gives:
For this specific input:
The model says this run performs 11 abstract operations.
The exact count has two parts:
As increases, increases. The constant does not.
For input sizes :
The exact count lies between two linear functions:
and
Both bounds hold:
The scan processes one item at a time. The array values do not change. Only the current index and completed-operation counts change.
The fixed setup work occurs before scanning begins.
| State | Current index | Current item | Comparisons completed | Prints completed | Index advances completed | Explanation |
|---|---|---|---|---|---|---|
| State 0 | 0 | 4 | 0 | 0 | 0 | Setup is complete. . The exact model is . |
| State 1 | 1 | 1 | 1 | 1 | 1 | Item 4 was compared, printed, and passed. |
| State 2 | 2 | 7 | 2 | 2 | 2 | Item 1 was compared, printed, and passed. |
| State 3 | 3 | none | 3 | 3 | 3 | Item 7 was compared, printed, and passed. The scan is finished. |
Now count the modeled operations.
So:
The count agrees with:
Each item causes the same three modeled actions, regardless of whether its value is 4, 1, or 7.
After processing some number of items, look at the completed work.
For example, after processing the first two items, 4 and 1:
1processed items: [4, 1]
2next index: 2
3
4comparisons: 2
5prints: 2
6index advances: 2The scan has completed exactly one comparison, one print, and one index advance for every processed item.
The loop invariant is:
For the stated counting model, after processing items, the algorithm has completed comparisons, prints, and index advances; only fixed setup and return work remains outside the per-item count.
The invariant gives a per-item contribution of and a final count of .
Start with the input length:
Scan from index 0 through index n - 1.
For every item:
That is three abstract operations per item under this model.
After all items are processed:
Add the fixed setup and return work:
Derive the asymptotic bounds.
For :
So is a concrete linear upper bound:
Also, for :
So is a concrete linear lower bound:
The upper and lower bounds are both linear:
The constants 3, 2, and 5 appear in the proof. The final label keeps only the growth class.
The pseudocode performs the scan and returns both the exact count from the stated model and its asymptotic classification.
1procedure analyzeScanAndPrint(items)
2 input:
3 items — a finite indexed sequence
4 returns:
5 a record containing:
6 exactCount — the stated abstract operation count
7 thetaLabel — the asymptotic classification
8 mutation:
9 does not modify items
10
11 1. n <- length(items)
12 2. i <- 0
13 3. setupOperations <- 1
14
15 4. while i < n do
16 5. compareForModel(items[i])
17 6. print(items[i])
18 7. i <- i + 1
19 end while
20
21 8. returnOperations <- 1
22 9. exactCount <- 3 * n + setupOperations + returnOperations
23 10. return { exactCount: exactCount, thetaLabel: "Theta(n)" }Helper contract:
1compareForModel(value)
2 input:
3 value — the current item
4 returns:
5 no value
6 mutation:
7 does not modify the item sequence
8 cost-model role:
9 represents the one abstract comparison assigned to each itemThe exact-count formula on line 9 is valid only for this stated model:
The formula does not state that every implementation in every language performs exactly machine instructions.
Use the original input:
1items = [4, 1, 7]
2index 0 1 2| Pseudocode line | State |
|---|---|
| Line 1 | n <- length(items) gives n = 3. |
| Line 2 | i <- 0. |
| Line 3 | setupOperations <- 1. |
Current state:
1n = 3
2i = 0
3setupOperations = 1| Pseudocode line | State change |
|---|---|
| Line 4 | i < n is 0 < 3, so enter the loop. |
| Line 5 | Perform the modeled comparison on items[0], which is 4. Comparisons completed: 1. |
| Line 6 | Print 4. Prints completed: 1. |
| Line 7 | i <- i + 1 changes i from 0 to 1. Index advances completed: 1. |
1printed: 4
2next index: 1| Pseudocode line | State change |
|---|---|
| Line 4 | i < n is 1 < 3, so enter the loop. |
| Line 5 | Perform the modeled comparison on items[1], which is 1. Comparisons completed: 2. |
| Line 6 | Print 1. Prints completed: 2. |
| Line 7 | i <- i + 1 changes i from 1 to 2. Index advances completed: 2. |
1printed: 4, 1
2next index: 2| Pseudocode line | State change |
|---|---|
| Line 4 | i < n is 2 < 3, so enter the loop. |
| Line 5 | Perform the modeled comparison on items[2], which is 7. Comparisons completed: 3. |
| Line 6 | Print 7. Prints completed: 3. |
| Line 7 | i <- i + 1 changes i from 2 to 3. Index advances completed: 3. |
1printed: 4, 1, 7
2next index: 3| Pseudocode line | State |
|---|---|
| Line 4 | i < n is 3 < 3, so leave the loop. |
| Line 8 | returnOperations <- 1. |
| Line 9 | exactCount <- 3 * 3 + 1 + 1 = 11. |
| Line 10 | Return { exactCount: 11, thetaLabel: "Theta(n)" }. |
The returned exact count is:
The returned asymptotic label is:
The proof must justify:
Before the loop begins, i = 0. No items have been processed.
So:
The invariant holds for .
Assume the invariant holds after processing items, where .
The next loop iteration processes items[i].
Each count increases from to . After the iteration, the invariant holds.
The loop ends when i = n. At that point, exactly items have been processed. The invariant gives:
That is:
The model also includes one setup operation and one return operation:
For every :
The inequality gives a linear upper bound:
For every :
The inequality gives a linear lower bound:
The function has both linear upper and lower bounds:
Both sides of the bound argument justify .
Start from the stated exact count:
For :
So the work is at most a constant multiple of :
Also:
So the work is at least a constant multiple of :
Together:
The loop processes every item once. Under this model, every input of size performs the same number of modeled per-item actions. There is no separate best-case or worst-case count here.
The algorithm stores only a fixed number of variables:
1n
2i
3setupOperations
4returnOperations
5exactCountThe algorithm does not allocate storage proportional to .
So auxiliary space is:
The input sequence and printed output are not counted as auxiliary space.
For simple polynomials with nonnegative input sizes, the highest-degree term is the dominant term.
For example:
has dominant term . Therefore:
A coefficient does not decide which term dominates. Consider:
Even though 100 is larger than the coefficient of , the quadratic term eventually grows more quickly than the linear term. Its classification is:
A constant function is different:
Its value does not grow with , so it is:
not .
For , the illustrative model gives:
That does not conflict with . Asymptotic notation concerns behavior for sufficiently large input sizes; the linear bounds above use the threshold .
Incorrect assumption
13n + 2 is O(3n + 2), but not O(n)Smallest exposing input
1n = 1
2T(1) = 5Wrong conclusion
The analysis keeps the expression only as and refuses .
Correction
For every :
Big O permits a constant multiple of . Therefore:
Incorrect claim
1The algorithm is O(n), so it performs exactly n operations.Exposing input
1n = 3
2T(3) = 11Wrong result
The claim predicts exactly 3 operations instead of the model’s 11 operations.
Correction
The exact model is:
The label states that the count has a linear upper-growth bound. The label does not state that the count equals .
Incorrect assumption
1100n + n^2 is Theta(100n)Exposing input
1n = 101At this input:
and
The quadratic term is already larger.
Wrong result
The analysis chooses the linear term because 100 is a large coefficient.
Correction
Compare how terms grow as increases. Degree matters more than a constant coefficient:
Incorrect assumption
1A function is at most n^2, so it is Theta(n^2).Exposing input
1T(n) = 7The function satisfies:
but it is not:
Wrong result
The analysis claims a quadratic tight bound without a quadratic lower bound.
Correction
Big Theta requires both bounds:
and
For , the matching upper and lower growth are constant:
Implement:
1classifyGrowth(expressionId)The input is one of these fixed identifiers:
1constant_7
2linear_3n_plus_2
3quadratic_n2_plus_n_plus_2
4cubic_n3_plus_4nReturn the expected Theta label for each expression:
| Expression identifier | Expression | Expected result |
|---|---|---|
constant_7 | Theta(1) | |
linear_3n_plus_2 | Theta(n) | |
quadratic_n2_plus_n_plus_2 | Theta(n^2) | |
cubic_n3_plus_4n | Theta(n^3) |
Executable tests verify each exact identifier-to-label mapping.
1def analyze_scan_and_print(items):
2 n = len(items)
3 i = 0
4 setup_operations = 1
5 while i < n:
6 # the modeled comparison is a no-op; only the print is visible
7 print(items[i])
8 i += 1
9 return_operations = 1
10 exact_count = 3 * n + setup_operations + return_operations
11 return exact_count, "Theta(n)"
12
13exact_count, theta_label = analyze_scan_and_print([4, 1, 7])
14print(f"exactCount={exact_count} thetaLabel={theta_label}")
15
16holds = all(3 * n <= 3 * n + 2 <= 5 * n for n in range(1, 1001))
17print("3n <= 3n + 2 <= 5n for n = 1..1000:", str(holds).lower())1public class Main {
2 static int analyzeScanAndPrint(int[] items) {
3 int n = items.length;
4 int i = 0;
5 int setupOperations = 1;
6 while (i < n) {
7 // the modeled comparison is a no-op; only the print is visible
8 System.out.println(items[i]);
9 i++;
10 }
11 int returnOperations = 1;
12 return 3 * n + setupOperations + returnOperations;
13 }
14
15 public static void main(String[] args) {
16 int exactCount = analyzeScanAndPrint(new int[]{4, 1, 7});
17 System.out.println("exactCount=" + exactCount + " thetaLabel=Theta(n)");
18
19 boolean holds = true;
20 for (int n = 1; n <= 1000; n++) {
21 if (!(3 * n <= 3 * n + 2 && 3 * n + 2 <= 5 * n)) holds = false;
22 }
23 System.out.println("3n <= 3n + 2 <= 5n for n = 1..1000: " + holds);
24 }
25}1#include <iostream>
2#include <vector>
3using namespace std;
4
5int analyzeScanAndPrint(const vector<int>& items) {
6 int n = items.size();
7 int i = 0;
8 int setupOperations = 1;
9 while (i < n) {
10 // the modeled comparison is a no-op; only the print is visible
11 cout << items[i] << endl;
12 i++;
13 }
14 int returnOperations = 1;
15 return 3 * n + setupOperations + returnOperations;
16}
17
18int main() {
19 int exactCount = analyzeScanAndPrint({4, 1, 7});
20 cout << "exactCount=" << exactCount << " thetaLabel=Theta(n)" << endl;
21
22 bool holds = true;
23 for (int n = 1; n <= 1000; n++) {
24 if (!(3 * n <= 3 * n + 2 && 3 * n + 2 <= 5 * n)) holds = false;
25 }
26 cout << "3n <= 3n + 2 <= 5n for n = 1..1000: " << (holds ? "true" : "false") << endl;
27}1function analyzeScanAndPrint(items) {
2 const n = items.length;
3 let i = 0;
4 const setupOperations = 1;
5 while (i < n) {
6 // the modeled comparison is a no-op; only the print is visible
7 console.log(items[i]);
8 i++;
9 }
10 const returnOperations = 1;
11 return { exactCount: 3 * n + setupOperations + returnOperations, thetaLabel: 'Theta(n)' };
12}
13
14const { exactCount, thetaLabel } = analyzeScanAndPrint([4, 1, 7]);
15console.log(`exactCount=${exactCount} thetaLabel=${thetaLabel}`);
16
17let holds = true;
18for (let n = 1; n <= 1000; n++) {
19 if (!(3 * n <= 3 * n + 2 && 3 * n + 2 <= 5 * n)) holds = false;
20}
21console.log(`3n <= 3n + 2 <= 5n for n = 1..1000: ${holds}`);Big O gives only an upper bound; Theta needs an upper and a lower bound. The function 7 is O(n^2), but it is not Theta(n^2), because nothing grows quadratically. It is Theta(1).
No. It says the count has a linear upper bound. With the lesson's model, T(3) = 11 operations, not 3, and the algorithm is still O(n).
Because a constant multiple absorbs them: 3n + 2 <= 5n once n >= 1. For 100n + n^2 at n = 101, n^2 is 10201 and 100n is 10100, so the quadratic term already wins.
No. Big O bounds how a function grows; worst case picks which input you measure. You can attach O, Omega or Theta to a best-case, average-case or worst-case count.
Paul Bachmann introduced the O symbol in 1894, and Edmund Landau popularised it. Donald Knuth proposed Omega and Theta for algorithm analysis in 1976.