Algorithm Analysis: From Basic Operations to Asymptotic Notation

This session turns the abstract idea of "how fast is an algorithm" into a precise, examinable craft. We begin with a recap of the five properties of an algorithm, then build the practical tool we will use all semester — the basic operation method — and drive it through worked examples (ArrayMax, matrix multiplication). The counting results lead to the central concept of the session, the order of growth, and then to the professional language that compares algorithms: asymptotic notation, with its big O, big omega, and big theta families, the formal definitions, worked proofs, and the little brothers little o and little omega. The session ends with the practical question of when an algorithm is worth calling correct at all.

2.1 The Five Properties of an Algorithm (Recap)

We begin with a recap of the five consolidated properties of an algorithm, because the whole course builds on this definition. An algorithm is a step-by-step procedure for solving a problem; last session we asked what makes a procedure an algorithm, and the answer was consolidated under exactly five headings. The class runs faster today, so these foundations matter — anyone who missed the previous session is at a real disadvantage, since everything that follows uses these terms.

2.1.1 The Five Properties

The five properties of an algorithm are input, output, definiteness, finiteness, and effectiveness. Each one pins down a requirement:

• Input — the algorithm takes some input values from a specified set.
• Output — it produces an output related to the input.
• Definiteness — every step is precisely defined and unambiguous; there is no room for interpretation.
• Finiteness — the algorithm ends after a finite number of steps.
• Effectiveness — every operation can be carried out, in principle, by a person using pencil and paper in a finite amount of time.

The warning that came with the recap was sharp: when asked for the properties of an algorithm, do not give generic answers like "efficient" or "unambiguous" — those are loose descriptions, not the consolidated headings. The five specific terms above are what the course uses, and the exam expects them. Exam note: expect to be asked for the properties of an algorithm using these exact five headings — input, output, definiteness, finiteness, effectiveness.

The vocabulary correction happened live, so it is worth recording in full. The student's answer "efficient" was not wrong in spirit — an efficient algorithm is a good algorithm — but it is the wrong heading. The property that says "each operation can actually be carried out, in principle, with pencil and paper in finite time" has a specific name: effectiveness. Efficiency (how little time or space an algorithm uses) is a performance question, and it belongs to the analysis topics that fill the rest of this session. Effectiveness is a structural question: it asks whether the operations are even executable at all. Mixing the two words loses the distinction the course needs later, when we say "the algorithm is effective but not efficient" — it works, but it is slow.

2.1.2 Euclid's Algorithm, Experimental Analysis, and the RAM Model

The recap covered the rest of the previous session. First, Euclid's algorithm — the ancient procedure for computing the greatest common divisor of two numbers — was examined to test whether it qualifies as an algorithm under the five properties; it does, and it is the running example of a procedure that satisfies every property. It takes two positive integers as input (input), returns their greatest common divisor (output), each division step is fully specified (definiteness), the remainder strictly shrinks so the loop must stop (finiteness), and every step is a plain arithmetic operation doable by hand (effectiveness).

Second, we revisited the two ways to study how fast an algorithm runs. The first is experimental analysis: we convert the algorithm into a program, execute the program, and measure the time each algorithm actually takes. The second is the RAM model (Random Access Machine model), a simplified, idealized computer on which we do not execute anything at all — instead we count the number of primitive operations the algorithm performs. Experimental studies had limitations (the machine, the language, the input data all distort the measurement), which is why we moved to the RAM model, and inside the RAM model we count primitive operations. Recall the vocabulary: a primitive operation is one of the small, fixed-cost operations the RAM machine can do — a basic arithmetic operation, a comparison, an assignment, and so on — and last session we had a specific list of examples of primitive operations.

The two approaches answer the same question — "how fast is this algorithm?" — in very different ways:

That last row is the bridge to the next section: counting every single primitive operation is too fine-grained to be practical. The course instead adopts a coarser tool — the basic operation method — which counts just one carefully chosen operation. That is exactly where Section 2.2 starts.

Real-world connection: the RAM-model philosophy — "analyze the algorithm, not the machine" — is the same thinking behind benchmark-free algorithm selection in industry. When a company compares two candidate algorithms, it does not want an answer that depends on which laptop ran the test; it wants a machine-independent comparison that stays valid when the software is deployed on different hardware. That is precisely what the order-of-growth analysis of the rest of this session provides.

2.2 The Basic Operation Method

Counting every primitive operation is too fine-grained. The method we will use throughout the course — the basic operation method — counts just one carefully chosen operation instead, and from that single count we derive the time complexity.

2.2.1 What Is a Basic Operation?

A basic operation is the operation that contributes the most towards the running time of an algorithm — equivalently, the statement that executes the maximum number of times. Do not confuse basic operations with primitive operations; the two terms are different. Primitive operations are the small building blocks; the basic operation is one specific primitive operation (or one statement) that dominates the running time.

The working assumption is that the two characterizations agree: the statement that executes the maximum number of times is also the one that contributes most to the running time. There can be cases where they differ — where the statement that executes most often is cheap and a rarely-executed statement is very expensive. In that situation, the tie-breaker is explicit: consider the operation that contributes the most towards the running time of the algorithm.

2.2.2 The General Steps for Non-Recursive Algorithms

The standard recipe for analyzing a non-recursive algorithm has five steps:

1. Decide on the parameter $n$ that indicates the input size.
2. Identify the algorithm's basic operation.
3. Check whether the number of times the basic operation is executed depends only on the input size $n$. This check matters because the time taken can depend on the type of input as well. Example: if the numbers are already sorted, some sorting algorithm barely works; if the numbers are completely unsorted, it works hard; if they are partially sorted, it takes some time in between. When the input type matters, you have to analyze the worst case, the average case, and the best case separately — a topic that comes later.
4. Set up a summation that reflects the number of times the basic operation is executed. The typical shape is $C(n)={\sum }_{\text{loop bounds}}1$, where $C(n)$ counts executions of the basic operation as a function of the input size $n$.
5. Simplify the summation using standard formulas (the arithmetic series ${\sum }_{i=1}^{n}1=n$, the series formula for ${\sum }_{i=1}^{n}i=\frac{n(n+1)}{2}$, and so on).

The whole course's analysis style rests on this recipe, so the sequence — input size, basic operation, dependency check, summation, simplification — is worth memorizing.

Real-world connection: this "count one dominant operation" habit is exactly how profiling works in industry. Engineers do not instrument every line of a system; they profile to find the hot path — the one function that consumes 90% of the time — and optimize only that. The basic operation is the algorithmic version of the hot path: find it, count it, and you know where the time really goes.

2.3 Worked Example: ArrayMax

The first worked example is the familiar ArrayMax algorithm: given an array of $n$ numbers, find the largest. The algorithm walks through the array with a loop, comparing the current element with the best found so far and updating the best when it finds something larger.

2.3.1 Finding the Basic Operation

The loop runs the index $i$ from 1 to $n-1$ (the first element is the initial best, so there is nothing to compare at position 0). Inside the loop, two candidate statements compete for the title of basic operation: the comparison of the current element with the current best, and the assignment that updates the best when the comparison succeeds.

The comparison wins, and the reason is the professor's key teaching point:

The general rule shown here: a statement that runs conditionally can be skipped, but the condition that decides it runs every time. So when you look for the statement that executes the maximum number of times, pick the comparison, not the assignment it guards.

The same logic repeats through the whole course. Any time you see if (condition) { do something }, the condition is the candidate basic operation, not the body of the if. The body might be skipped on some inputs; the condition is evaluated on every pass. This is why loop-based searches (like the element-uniqueness exercise of Section 2.5.4) almost always end up with the comparison as the basic operation.

2.3.2 Counting Executions: T(n) = n − 1

Input size is $n$. Basic operation is the comparison in the loop. The count does not depend on the worst case or the best case: we do not check any condition about whether the first element is largest or the last element is largest — the loop marches through the entire array regardless of the order of the numbers, so every input of size $n$ triggers the same number of comparisons.

Let $T(n)$ denote the number of comparisons — the time taken expressed as a function of the input size $n$. The loop runs the comparison once per iteration, and the loop goes from $i=1$ to $n-1$, so

$$T(n)=\sum _{i=1}^{n-1}1=(n-1)-1+1=n-1.$$

The professor's phrasing while writing this: the sum's upper limit follows your loop condition — if the loop runs to $n$, the count is $n$; here the loop runs to $n-1$, so the count is $n-1$. The middle step is the standard summation rule: number of terms = upper limit minus lower limit plus 1, giving $(n-1)-1+1=n-1$. The sum of $1$'s counts the constant time taken by the one basic operation per iteration — "there is only one statement which will take some constant time."

The result: the time taken by ArrayMax is $n-1$ — the simplest algorithm and the simplest calculation. In words: the loop runs n minus 1 times, so the count is n minus 1.

2.3.3 What About the Increment?

A natural doubt: the loop counter also runs every iteration, so why do we not count it too? The professor's answer is a small but important lesson about what "count" means:

In other words, including the increment doubles the counted constant but leaves the function $n-1$ (or $2(n-1)$) with the same order of growth. Because we measure how the count grows with $n$, a constant factor of 2 changes nothing about the conclusion. This is the first taste of the order-of-growth idea developed in Section 2.6.

Real-world connection: the "conditional statement can be skipped, the condition always runs" rule is why database query planners and compilers optimize the test in hot loops rather than the rare update inside the branch. The condition is paid for unconditionally, on every record or every iteration; the branch body is a bonus cost that many inputs never pay.

2.4 Worked Example: Statements with Different Timings

This hypothetical example isolates a different question: when statements have different costs, which one decides the running time? It is a deliberately artificial setup — the professor said not to take the numbers literally — but it is the cleanest way to build the intuition that the slowest statement rules.

2.4.1 The Setup and the Answer

Suppose an algorithm has five statements, each with a different time cost:

(There was a sixth statement, ignored for the exercise.) Five statements with different timings — which one is the basic operation? The answer: statement 5, because it takes the most time (1.5 ms). Statement 4 at 1 ms is the runner-up, but the basic operation is the single statement that takes the most time, not the second-most.

2.4.2 Why Not All Statements? (The Parallel-Execution Intuition)

A student proposed that the basic operation should be the sum of all the statements. The professor rejected the sum outright and gave the parallel-execution analogy:

The mental model: if all statements execute in parallel, the job is done only when the slowest statement is done — "when statement 5 or when statement 4 is executed, that is the time taken by the algorithm." If you cannot digest the method, the professor's advice is to assume parallel execution of all statements and let the slowest one set the finish time.

A follow-up question pushed on the analogy itself:

The numbers in the setup make the point concrete: 0.25 ms is a quarter of statement 4's 1 ms, so statement 3 finishes long before the bottleneck statement. "Come out of the box. Think outside the box" — that is the nudge that accompanied this exchange.

Then came the sharpest objection, which the professor turned into a foundational warning:

The deeper point: algorithm analysis deliberately happens before any machine or language exists. We do not know whether the company we work for will give us a one-core machine or a four-core machine, and we do not know which programming language we will be asked to code in. So none of that enters the analysis — the analysis is purely about the algorithm itself. Exam note: when asked which statement is the basic operation, the answer is the statement that takes the most time, never "the sum of all the statements."

Real-world connection: the slowest-statement rule is the principle behind bottleneck analysis in manufacturing and software systems — a production line is only as fast as its slowest station, and a web request is only as fast as its slowest dependency (database query, external API, image server). Engineers find the bottleneck and fix that one component; speeding up the already-fast parts changes nothing. Same rule, same reason.

2.5 Worked Example: Matrix Multiplication

The second worked example is matrix multiplication — the classic case where the counting produces a power of $n$, and the classic lesson in interpreting what $n^3$ means.

2.5.1 The Algorithm and the Shape Rule

The algorithm multiplies two square matrices $A$ and $B$, each of order $n\times n$, and produces the product matrix $C=A\times B$, also $n\times n$. The professor flagged the shape rule so nobody confuses this special case with the general rule: normally, if $A$ is of order $m\times n$ and $B$ is of order $n\times p$, we can multiply them and the result is of order $m\times p$. Here everything is $n\times n$ — both factors square, so the general rule collapses to the square case. Do not confuse the two.

The algorithm, in pseudocode, is the definition-based triple loop:

$$\text{for }i=0\text{ to }n-1,\text{for }j=0\text{ to }n-1,\text{for }k=0\text{ to }n-1:C[i][j]=C[i][j]+A[i][k]\times B[k][j]$$

The outer two loops initialize the cells of $C$; the inner loop accumulates the dot product. All three loops run from 0 to $n-1$.

2.5.2 Counting: T(n) = n³

Input size is $n$. Which statement is the basic operation? The candidate list included "computation of $C[i][j]$", "assignment", "multiplication", and "for loop". The professor rejected the last one dramatically — "don't give me this for loop, that breaks my heart":

The full reasoning: the statement $C[i][j]=C[i][j]+A[i][k]\times B[k][j]$ bundles a multiplication and an addition. Because the two can be written as two separate statements, we may pick either one — but the multiplication must be in the basic operation. "Computation of $C[i][j]$" is acceptable as an answer, but "multiplication" is the more specific one. A related question settled the addition-versus-multiplication choice:

Does the count depend on the worst case or the best case? No — whatever numbers are in the matrices, as long as they are square, the algorithm walks the entire structure. Every input of size $n$ triggers the same number of multiplications.

The count is the triple sum — one unit of constant time for the basic operation, per execution, over all three loops:

$$T(n)=\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}\sum _{k=0}^{n-1}1=n^3$$

Each sum contributes a factor of $n$, so expanding the summations gives $n$ times $n$ times $n$: the basic operation executes $n^3$ (n cube) times. The professor noted you may name the counting function as you like — call it $M(n)$ for the number of multiplications, say — but the usual convention is $T(n)$ for the time taken. And $n$ here is the input size, not a loop variable.

2.5.3 Interpreting n³

The result $T(n)=n^3$ is not just a number — it is a promise about how the algorithm scales. The interpretation the professor drilled:

• When the size of the input is 2, the order of the time taken is $2^3=8$.
• When the size of the input is 3, the order of the time taken is $3^3=27$.
• When the input size is doubled, the time taken grows $2^3=8$ times.
• When the input size is tripled, the time taken grows $3^3=27$ times.

Compare with ArrayMax: its time was $n-1$, so doubling the input doubles the time (roughly). Here doubling the input multiplies the time by eight. That contrast — how the time responds to the input size — is the entire subject of the next section.

2.5.4 Your Turn: Element Uniqueness

The professor assigned the element uniqueness problem (check whether every element of an array is distinct) as a self-study exercise, with a hint that makes it easy: the provided algorithm has only one statement, so there is no other option — the comparison is forced to be the basic operation. The calculation then follows the same pattern as ArrayMax and matrix multiplication: identify the basic operation, count executions, simplify the summation.

Real-world connection: matrix multiplication is the inner engine of graphics pipelines (transformation matrices), neural network training (weight-matrix updates), and scientific simulation (solving linear systems). That is why an algorithm that beats $n^3$ — like Strassen's $n^{2.81}$, or library routines tuned for $n^3$ but with tiny constants — is worth billions: doubling a problem's size costs 8× with $n^3$ but only about 7× with $n^{2.81}$, and for $n=10,000$ that constant gap is real money in GPU-hours.

2.6 Order of Growth

We now step back and ask what the results $n-1$ and $n^3$ really tell us. The answer is the concept of order of growth, and it is the bridge between counting operations and comparing algorithms.

2.6.1 Definition

The order of growth of an algorithm is how the value of $n$ — the input size — affects the time complexity of the algorithm; how the time complexity changes with respect to $n$. The professor's working definition: how the value of $n$ affects the time complexity of an algorithm is called the order of growth of an algorithm.

So when we say "the order of growth is $n^3$", we mean: when the input size is doubled, the time taken increases $2^3=8$ times; when the input size is made 4 times, the time taken increases $4^3$ times. The phrase "the time complexity is a function of the input size" is exactly this idea — the function says how the time responds as the input grows.

2.6.2 The Function Classes

The running time of an algorithm can fall into a small set of standard classes, and the course uses these terms only:

"Logarithmic" means $\log n$, where $n$ is the input size. "Linear" means $n$. "$n\log n$" means $n\log n$ — there is no other way to write it. "Quadratic" is $n^2$, "cubic" is $n^3$, "exponential" is $2^n$ — and do not confuse quadratic with exponential; exponential means $2$ raised to the power $n$. Factorial, $n!$, was not on the professor's slide list but is a legitimate order of growth (more on that below).

2.6.3 Comparing Orders of Growth

With the classes defined, the professor ran a sequence of mini-comparisons, each with a rule to extract:

$n(n+1)+200n^2$ vs $200n^2$. Two students wrote algorithms for the same problem: one whose time is $n(n+1)+200n^2$, the other $200n^2$. Which is better? Answer: they are the same — both are quadratic. The reason: the highest-order term has the same power in both. $n(n+1)+200n^2=n^2+n+200n^2=201n^2+n$, so the leading term is $n^2$; the other is exactly $200n^2$. Same highest power, same order of growth. The professor's generic rule: the highest-order term decides.

But the follow-up sharpened what "same" means:

The lesson: when we explain time complexity, there is a range after which the comparison becomes effective. We are not talking about small numbers — we are talking about $n$ very large. This is exactly the asymptotic behavior that motivates Section 2.7. "Asymptotic" means approaching a large value but never reaching it — assume it to be a very large one. The notations of the next section are defined for very large values of $n$; do not confuse the picture by plugging in 1 and 2.

$100n^2$ vs $0.01n^3$. Which is larger? $0.01n^3$ is larger in order of growth. At $n=1$ the assumptions break (100 vs 0.01), but do not go with small values of $n$ and confuse yourself. We are talking about order of growth: as the input size changes, $100n^2$ grows slower than $0.01n^3$, so $100n^2$ has the lower order of growth. Even though $100n^2$ starts 10,000 times larger at $n=1$, the cubic function eventually overtakes it — solve $100n^2=0.01n^3$ to find the crossover at $n=10,000$, and for any $n$ beyond that the cubic is larger forever.

${\log }_{2}n$ vs $\ln n$. Natural log vs base-2 log — same order of growth. The professor pointed to the change-of-base formula and told everyone to refresh logarithms and exponents, referring to textbook section 1.3.2. The derivation: ${\log }_{2}n={\log }_{e}n/{\log }_{e}2=\ln n/\ln 2$. The denominator $\ln 2$ is a constant, and constants are ignored in comparisons, so

$${\log }_{2}n=\frac{\ln n}{\ln 2}⟹{\log }_{2}n\text{ and }\ln n\text{ have the same order of growth.}$$

"When I say same order of growth, I am not talking about the values being equal. I am not even bothered about that." The two functions are different functions — ${\log }_{2}n$ and $\ln n$ give different numbers — but they are the same class: one is a constant multiple of the other, and constant multiples are invisible at the order-of-growth level. This is why textbook complexity statements freely write $\log n$ without specifying the base.

$2^{n-1}$ vs $2^n$. Same order of growth — two to the power $n$ minus one equals $2^n$ divided by 2:

$$2^{n-1}=\frac{2^n}{2}$$

and $\frac{1}{2}$ is a constant, so it is ignored — the two have the same order of growth. Exam note: if you can answer these four comparison questions (same-power polynomials, $100n^2$ vs $0.01n^3$, log-base change, $2^{n-1}$ vs $2^n$), the order-of-growth topic is done.

2.6.4 Predicting Time When the Input Size Doubles

The most exam-relevant skill is translating an order of growth into a concrete time prediction. The professor ran three questions, all with the same setup — a program that takes 5 seconds for an input of size $n$ — and each time the input size is doubled.

Order of growth $n^2$. When the input is $n$, the time taken is proportional to $n^2$. When the input is $2n$, the time is $(2n{)}^2=4n^2$ — four times the original. So the answer is $4\times 5=20$ seconds. The class produced a shower of wrong answers (25, 15, 10, 100) before the professor landed on 20; one student's "100" drew the deadpan response that if the answer were 100, the professor would leave the class. The lesson: doubling the input quadruples the time for a quadratic algorithm.

Order of growth $n$. Linear: time is proportional to $n$. Doubled input means double the time: $2\times 5=10$ seconds. "I don't want to see any other answer than 10 seconds."

Order of growth $n^3$. Cubic: $(2n{)}^3=8n^3$, so the time becomes $8\times 5=40$ seconds. "I don't want to see any other answer than 40 seconds."

The pattern: doubling the input multiplies the time by $2^{\text{order exponent}}$ — $2^1=2$ for linear, $2^2=4$ for quadratic, $2^3=8$ for cubic. Study advice: if any of this doubling logic did not land, sit down calmly after class and redo the calculations by hand — "you have to somehow get that. I will not explain it any better."

2.6.5 The Growth Table at Small Input Sizes

To make the classes tangible, the professor evaluated them at a small input size, $n=4$ (using base-2 logarithms):

Already at such a small input the variation is visible — and the exponential class (16) sits below the cubic class (64). Why? Because the input size is small. We are not bothered by that: we find the value of $n$ after which the exponential class takes over, and only then do we say the comparison holds. There exists a threshold $n$ beyond which the ordering of the classes is the ordering you expect (constant < log < linear < $n\log n$ < quadratic < cubic < exponential < factorial).

At $n=1$, every polynomial class takes 1 unit (the log classes take 0, since ${\log }_{2}1=0$), and only the exponential class takes 2 — so even at the smallest input, the exponential algorithm is already slower than the constant one. The professor's point: even when the input size is 1, the exponential algorithm is taking more time.

One more practical warning came with the table: "There may even be some situations in which the constant is so huge in a linear algorithm that even an exponential algorithm with a small constant may be preferable in practice." A linear algorithm with an enormous constant can lose to an exponential algorithm with a tiny constant — for realistic input sizes. "But then, we are worried only about large values of $n$."

2.6.6 Quick Order-Identification Exercise

The professor drilled the class with functions to classify by their order of growth. Each answer, with the reasoning:

A note on classification vocabulary: "cubic, quadratic, everything can be combined under polynomial" — polynomial is the umbrella term — "but be specific. If you are able to write it as specific, be specific. This is cubic."

A question from the class about the missing factorial class got a practical answer:

And the polynomial-vs-specific distinction, captured as a vocabulary correction:

2.6.7 Counting Nested Loops: Rules of Thumb and an Exam Warning

The quick way to estimate the order of growth of nested loops: if there are two loops each going from 0 to $n$ (or 1 to $n$), the time is $n^2$; if there are three loops, it is $n^3$. The professor's first refinement: check whether the loops go from 1 to $n$ or from 0 to $n$ — the bound matters for exact counts, though not for the order.

The exam warning that followed is one of the most important lines in the whole session:

The example that completed the lesson had non-identical bounds: an $i$ loop going from 0 to $n$, and inside it a $j$ loop going from $i$ down to 0. When $i$ is $n$, the inner loop still comes down to 0, so the number of executions of the single basic operation (the summation) is

$$\sum _{i=0}^n(i+1)=\frac{(n+1)(n+2)}{2}\in \Theta (n^2)$$

and the answer is $\Theta (n^2)$ — with the reason stated, not asserted from the number of loops.

2.6.8 Why We Care: The Prime-Checking Example

To motivate all of this, the professor posed a question: why should we care about order of growth at all? The answer was a head-to-head comparison of two algorithms for the same problem — checking whether a given number $n$ is prime.

Algorithm 1 divides $n$ by every number from 2 to $n-1$. There is nothing wrong with this algorithm as a procedure — but the moment you analyze its complexity, it loses. In the worst case (the number is prime, so every division must be tried), the number of division operations is $n-2$. Assume one millisecond per division: for $n=11$, the time taken is $11-2=9$ (units); for $n=101$, it is $101-2=99$.

Algorithm 2 divides $n$ only by the numbers from 2 to $\sqrt{n}$. In the worst case the loop runs $\sqrt{n}-1$ times (call it $\sqrt{n}-1$, where $n$ is the input size). For $n=11$: $\sqrt{11}\approx 3$, so $3-1=2$ units. For $n=101$: $\sqrt{101}\approx 10$, so $10-1=9$ units.

Even at such a small input size, the difference is stark: 99 units vs 9 units. An efficient algorithm completes the job in 9 milliseconds while the other algorithm is still executing. That is the reason we study order of growth: the two algorithms have orders of growth $n^1$ (Algorithm 1) and $n^{1/2}=\sqrt{n}$ (Algorithm 2), and the gap between $n$ and $\sqrt{n}$ only widens as $n$ grows. Exam note: this is the canonical example of why complexity analysis beats "it works" — the faster algorithm wins the comparison on any realistic input.

2.6.9 A Peek at Best and Worst Cases

Right before moving to asymptotic notation, the professor teased the next topic with an example (the input-type dependence from Step 3 of the recipe). For an algorithm that scans an array for the maximum and keeps an assignment counter: in the best case, the very first element is already the maximum, and the time taken is $5n$. In the worst case, it is $7n-2$. The definitions previewed: the best case is where the algorithm takes the least time to execute; the worst case is where it takes the maximum time to execute. Full treatment comes in a later session.

Real-world connection: the prime-checking contrast is exactly why cryptographic systems choose the input sizes they do. Modern RSA keys are hundreds of digits long; the security argument depends on factoring and primality tasks being just hard enough — a $\sqrt{n}$-style improvement in primality testing is welcomed, while an unexpectedly fast factoring algorithm (an $n$-order jump in the other direction) would force every certificate authority to lengthen its keys overnight. Order of growth is the language in which such security margins are debated.

2.7 Asymptotic Notation: The Informal Definitions

We already know what order of growth is — how the time taken by an algorithm grows with respect to $n$. But knowing the orders is not enough; we still need a professional language to compare algorithms. That language is asymptotic notation.

2.7.1 Why We Need Asymptotic Notation

The precise meaning of the word "asymptotic" is the most important fact about it, and it is easy to ignore: how the running time of an algorithm increases with the input size, as the size of the input increases without bound. As $n$ approaches infinity — that is when we talk about order of growth and asymptotic notation.

The motivating problem: I know algorithm 1 takes $n$ time and algorithm 2 takes $n^3$ time, but how do I say, professionally, that one is better than the other? I need some notation to write it down: the time taken by algorithm 1 is, say, big O of $n$; the time taken by algorithm 2 is big O of $n^3$ — and now the comparison is written down. Real-world: this is exactly the situation at work — tomorrow, you and a colleague are each asked to write an algorithm for the same problem; you submit both, and the manager has to choose. The one with the better order of growth gets the project. Asymptotic notations are the notations used to compare algorithms based on the order of growth of their basic operations, as the size of the input increases without bound.

The three main notations are big O, big omega ($\Omega$), and big theta ($\Theta$). Why the word "asymptotic"? Because the whole discussion assumes the input size grows without bound.

2.7.2 Big O: Lower-or-Same Order of Growth

Let $g(n)$ be the order of growth of some algorithm. The informal definition: $O(g(n))$ is the set of all functions with a lower or same order of growth as $g(n)$ — to within a constant multiple, as $n$ goes to infinity. The two clauses in brackets are implicit: whenever you hear "asymptotic notation", assume "as $n$ goes to infinity" and "to within a constant multiple".

Membership works like a set. Suppose $g(n)=n^3$. Then:

• $n\in O(n^3)$ — an algorithm with order of growth $n$ has a lower order of growth than $n^3$, so it belongs.
• $n^4\notin O(n^3)$ — an algorithm with order of growth $n^4$ grows much faster than one with order $n^3$; its time grows faster, so it is outside the set.

In words: everything that grows no faster than $g(n)$ lives inside $O(g(n))$.

2.7.3 Big Omega: Higher-or-Same Order of Growth

$\Omega (g(n))$ is the set of all functions with a higher or same order of growth as $g(n)$. The mirror image of big O. Following the same membership logic:

• $n\notin \Omega (n^3)$ — the order of growth of $n$ is lower than the order of growth of $n^3$.
• $n^4\in \Omega (n^3)$ — higher order of growth, so it belongs.
• $n^3\in \Omega (n^3)$ — same order of growth, so it belongs.

The key sentence that ties O and $\Omega$ together: $n^3$ is an element of big O of $n^3$ and an element of big omega of $n^3$, because big O takes lower-or-same growth and big omega takes higher-or-same growth.

2.7.4 Big Theta: Same Order of Growth

$\Theta (g(n))$ is the set of all functions with the same order of growth as $g(n)$. Theta means the order of growth matches exactly. If an algorithm has order of growth $n^2$, then every algorithm with the same $n^2$ order of growth can be expressed as $\Theta (n^2)$. For example, $n^2+2n+3\in \Theta (n^2)$. This comparison applies to polynomials in $n$ — "we are talking about time complexity in the order of $n$ with respect to $n$."

The informal picture is complete: O is the upper family, $\Omega$ the lower family, $\Theta$ the exact match.

2.7.5 Student Questions

Two questions from the class sharpened the informal picture:

The professor accepted the student's claim, and the precise value of $n$ where the coincidence happens is easy to check: $100n^2=0.1n^3$ when $n^3/n^2=100/0.1=1000$, that is, at $n=1000$ — where both functions equal $10^8$. (At $n=100$ they do not coincide: $100\cdot 100^2=10^6$ while $0.1\cdot 100^3=10^5$.) The lesson is not the exact value but the phenomenon: two different orders of growth can still take the same value at isolated points, so a claim of the form "$f$ grows no faster than $g$" cannot be verified one point at a time. That is why the formal definition (Section 2.8) uses constants and a threshold: it says "for all large $n$, up to a constant factor".

So membership in all three notations is possible; it happens exactly when the function has the same order of growth as $g(n)$.

Real-world connection: this set-based way of speaking ("$n\in O(n^3)$") is how engineers state capacity contracts: "our service handles up to $O(n)$ requests per second for $n$ servers" is a guarantee about growth — add servers and the capacity grows linearly — which is exactly the property a manager can budget against, ignoring constant factors like which cloud provider.

2.8 Big O: Formal Definition and Worked Proofs

The informal definition tells you what big O means; the formal definition tells you how to prove membership. This section builds the formal machinery and works two proofs in full, plus a graphical view.

2.8.1 The Formal Definition

Let $f$ and $g$ be functions from the non-negative integers to the non-negative reals. The domain-and-codomain clause matters — the time taken is always positive, so both sides are non-negative; "we never check this, assuming that the time taken will be always positive."

Definition. $f(n)\in O(g(n))$ if and only if there exists a real constant $c>0$ and an integer constant $n_0\ge 1$ such that

$$f(n)\le c\cdot g(n)\text{for every integer }n\ge n_0.$$

Three pieces deserve unpacking. First, the constant $c$: the definition says "to within a constant multiple" — $c$ scales $g$ up or down. Second, the constant $n_0$ ("n zero"): the claim holds only from some threshold onward. Third, the graph picture: $c\cdot g(n)$ should be above $f(n)$ — the line $f(n)$ stays below the line $c\cdot g(n)$, but only after $n_0$. Before $n_0$, we cannot predict which function is bigger; $n_0$ is the point after which the inequality is guaranteed.

Why constants and thresholds at all? The class asked exactly this, and the answer connects back to the small-$n$ warnings:

Two more clarifications that came up in the chat:

One remark on the formal definition in practice: only the highest-order term matters. When you write $f(n)\le c\cdot g(n)$, you can put any constant in front of the highest term — "I can write $3n\le c\cdot n^3$; it does not matter; only the highest term matters." A theorem in the textbook states this formally: constants and lower-order terms can be ignored in asymptotic comparisons.

2.8.2 The Table Method for Finding c and n₀

To prove $f(n)\in O(g(n))$ you must produce a specific constant $c$ and a specific constant $n_0$ and then show the inequality holds for all $n\ge n_0$. The goal is to find a pair $(n_0,c)$ and verify it. The professor's practical method for finding the pair is the table method:

1. Randomly substitute values for $n$ (1, 10, 100 — convenient numbers).
2. For each, compute $f(n)/g(n)$.
3. From $f(n)\le c\cdot g(n)$, the ratio gives a candidate $c\ge f(n)/g(n)$. Round the ratio up to a nice constant.
4. Each row gives a valid pair $(n_0,c)$ — and the pairs must be used consistently: if you pick $n_0=1$, you must use the $c$ from the $n=1$ row, not a $c$ from another row.

Proving any one valid pair is enough to prove big O. "You will find different methods to prove this... Stick to any one." Note that the $f/g$ ratio is computed because the definition rearranges to $c\ge f(n)/g(n)$ — that is where the constant comes from.

2.8.3 Worked Proof: 3n + 7 ∈ O(n)

Claim: $f(n)=3n+7$ is in $O(n)$, with $g(n)=n$. We know by looking that the highest term of $f$ is $3n$ and $g$'s highest term is $n$ — same order of growth, constants ignored — so it is in big O of $n$. But the proof:

Step 1 — find candidate pairs. Substitute convenient values of $n$ and compute $f(n)/g(n)$:

The three rows give three valid pairs: $(n_0=1,c=10)$, or $(n_0=10,c=4)$, or $(n_0=100,c=4)$. Any one of them proves the claim. Do not mix: $n_0=1$ goes with $c=10$, not $c=4$.

Step 2 — prove the inequality for the chosen pair. Take $(n_0=1,c=10)$. We must show

$$n\ge 1⟹3n+7\le 10n.$$

The professor's rule: start from the lowest-order term. Here $7$ is the lowest-order term, so we work on it first. Since $n\ge 1$, we have $7n\ge 7$. Replace the $7$ in $3n+7$ by the larger $7n$:

$$3n+7\le 3n+7n=10n.$$

So $3n+7\le 10n$ for every $n\ge 1$, which is exactly $f(n)\le c\cdot g(n)$ with $c=10$ and $n_0=1$. The proof is complete. The professor's commentary: "It is a very simple proof but a bit indirect way. First we have to understand what we are trying to do" — find $c$ and $n_0$ such that the definition's inequality holds — "and it might take a bit of time for you to digest this. But you will get it."

2.8.4 Worked Proof: n² + 2n + 1 ∈ O(n²)

Claim: $f(n)=n^2+2n+1$ — "n square plus two n plus one" — is in $O(n^2)$, with $g(n)=n^2$. Same two-step shape.

Step 1 — find candidate pairs.

Two valid pairs: $(n_0=1,c=4)$ or $(n_0=10,c=2)$. Pick the pair that is comfortable to work with — the professor picked the first.

Step 2 — prove the inequality. With $(n_0=1,c=4)$, we must show

$$n\ge 1⟹n^2+2n+1\le 4n^2.$$

Work on the lowest-order term repeatedly, converting it to the next-higher-order term each time. First, the constant $1$: since $n\ge 1$, we have $1\le n$, so replacing $1$ by $n$ only grows the polynomial:

$$n^2+2n+1\le n^2+2n+n=n^2+3n.$$

Now the lowest-order term is $3n$: since $n\ge 1$, we have $3n\le 3n^2$, so

$$n^2+3n\le n^2+3n^2=4n^2.$$

Chain the two steps: $n^2+2n+1\le n^2+3n\le 4n^2$, so the inequality $f(n)\le 4g(n)$ holds for all $n\ge 1$. Done.

The professor's reaction to the blank faces: "All of you are in blank. It would be easy to understand if you imagine graphically." The repeated move is always the same — take the lowest-order term, convert it to the next-higher-order term, repeat until the expression reaches the target $c\cdot g(n)$.

The same question the class raised, and the professor's re-explanation:

2.8.5 The Graphical View: 2n + 10 ∈ O(n)

The same ideas become visual with a plot. Claim: $2n+10\in O(n)$, with $g(n)=n$. Plot the blue line $2x+10$ and the red line $g(n)=n$: the blue line stays above the red line everywhere, so we cannot claim $2n+10\le n$ — the constant $c$ is genuinely needed.

Compute a candidate $c$: $2n+10\le c\cdot n$ leads to a value of $c=3$. Plot the green line $3n$. Now there is a crossing point — around $n=10$ — and for every $n$ beyond it, the green line $3n$ sits above the blue line $2n+10$:

$$2n+10\le 3n\text{for all }n\ge 10.$$

Before the crossing we cannot predict the behavior of the functions; after it we are sure. That crossing value is $n_0=10$, and the constant is $c=3$. This is precisely the "find a number after which the function holds true" idea, drawn instead of proved.

A free online graphing tool, or a small Python plotting script, will reproduce these lines — the script is the kind of thing to keep for checking such graphs by hand.

2.8.6 Practice and the Theorems

The professor promised to post 10 to 12 practice functions for order-of-growth and big-O work. The study advice attached to them: try every problem yourself first, and only then check the solutions; solutions are hidden until someone attempts each problem — if nobody posts doubts, the assumption is that everyone understood. Exam note: proving the textbook's theorems (constants and lower-order terms can be ignored, and the other theorems in the chapter) will not be asked in the exam — the textbook covers them directly, so read them there.

Real-world connection: the table method mirrors how engineers sanity-check performance claims: pick a few representative sizes, compute the ratio of the two functions, and confirm it stays bounded. And the $(n_0,c)$ pair is literally the "service-level objective" of a performance guarantee — "after our warmup period $n_0$, response time stays under $c\cdot$ (reference curve)" — the same two numbers, in a production monitoring dashboard.

2.9 Big Omega: Formal Definition and Worked Proof

If you understood the formal definition of big O, big omega is exactly the same concept — with the inequality flipped.

2.9.1 The Formal Definition

Definition. $f(n)\in \Omega (g(n))$ if and only if there exists a positive constant $c>0$ and a positive integer $n_0\ge 1$ such that

$$f(n)\ge c\cdot g(n)\text{for all }n\ge n_0.$$

Conceptually identical to big O: find a constant $c$ and a constant $n_0$, and show the inequality holds from $n_0$ onward. The difference is the direction — now $f(n)$ must sit above $c\cdot g(n)$ instead of below it.

2.9.2 Worked Proof: 3n + 7 ∈ Ω(n)

We already proved $3n+7\in O(n)$; the same function is also in $\Omega (n)$. With $f(n)=3n+7$ and $g(n)=n$, we need $c$ and $n_0$ such that $3n+7\ge c\cdot n$ for all $n\ge n_0$.

The ratio flips: for big O we computed $f(n)/g(n)$; for big omega we compute $g(n)/f(n)$. At $n=1$, $g/f=1/10$, which gives $c=1$. The chosen pair: $(n_0=1,c=1)$. The proof:

$$n\ge 1⟹3n+7\ge 3n\ge n.$$

The move differs from the big O proof. In big O we converted the lowest-order term to the next-higher-order term; in big omega the proof simply drops the lower-order term — the $+7$ only adds to the value, so throwing it away makes the left side smaller, and the inequality $3n+7\ge 3n$ is immediate. Then $3n\ge n$ for $n\ge 1$. so $3n+7\ge 1\cdot n$ for all $n\ge 1$. Done.

The question that came up about the flipped ratio:

The reasoning in detail: big O's requirement $f(n)\le c\cdot g(n)$ rearranges to $c\ge f(n)/g(n)$ — the constant must be at least the ratio of the two functions. Big omega's requirement $f(n)\ge c\cdot g(n)$ rearranges to $c\le f(n)/g(n)$ — or equivalently $c\cdot f(n)/g(n)$ works from the other side, $c\ge g(n)/f(n)$. The division flips precisely because the inequality flips; the two notations are mirror images in every mechanical step.

2.9.3 Big O Is an Upper Bound; Big Omega Is a Lower Bound

The two notations get their standard names from these pictures. Big O is called the asymptotic upper bound: $O(n^3)$ collects all functions with a smaller or same order of growth as $n^3$ — everything that grows no faster — so it bounds the function from above. Big omega is called the asymptotic lower bound: $\Omega (n^2)$ collects all functions with a same or higher order of growth than $n^2$ — everything that grows no slower — so it bounds the function from below.

A consequence for analysis: once you have computed an order like $n^5+n+3$, you do not even consider the $n+3$ part — a theorem states that constants and lower-order terms are ignored in these bounds. The bound is read from the highest-order term alone.

Real-world connection: lower bounds are the language of impossibility and guarantees in industry — "no algorithm can sort faster than $\Omega (n\log n)$ on comparison alone" tells a company that a claimed $O(n)$ sorter cannot exist, saving months of wasted engineering. Upper bounds are achievable promises ("our product runs in $O(n^2)$"); lower bounds are physics ("you can never do better than $\Omega (n\log n)$").

2.10 Big Theta: The Tight Sandwich

Big theta is the notation for an exact match — and the only one with a catch.

2.10.1 The Formal Definition

Definition. $f(n)\in \Theta (g(n))$ if and only if there exist positive constants $c_1>0$ and $c_2>0$ and a non-negative integer $n_0\ge 0$ such that

$$c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)\text{for all }n\ge n_0.$$

Note the catch: this time there are two constants, and $f(n)$ is sandwiched between them — $f(n)$ must sit between $c_1\cdot g(n)$ and $c_2\cdot g(n)$, for every $n$ from the threshold $n_0$ onward. Also note $n_0$ is now non-negative (the definition allows $n_0\ge 0$, whereas big O and big omega used $n_0\ge 1$).

Because the sandwich forces $f$ to be within constant multiples of $g$ both from above and from below, $\Theta (g(n))$ is exactly the set of functions with the same order of growth as $g(n)$ — matching the informal definition from Section 2.7.

2.10.2 Worked Proof: 5n² ∈ Θ(n²)

The professor's remark: "Here we are not going to use that tabular method to show the proof. Because it is direct."

How do you prove $5n^2\in \Theta (n^2)$ — five n square in theta? Either prove $f(n)\in \Omega (g(n))$ and $f(n)\in O(g(n))$, or — simpler here — find a value of $c$ so that the left-hand side equals the right-hand side. Take $c_1=c_2=5$:

$$5\cdot n^2\le 5n^2\le 5\cdot n^2.$$

Both sides equal $5n^2$, the middle is $5n^2$, so the sandwich holds with the same constant on both sides — the moment the two sides are equal, we may say the function is in $\Theta (n^2)$. That is the direct proof: look at the function, find a constant making the sides match, and the theta membership follows. The general strategy for proving theta membership: show the function is both big O and big omega of the target, or find the sandwich constants directly.

Real-world connection: theta is the notation of matching guarantees — a service that promises both "never faster than $c_{1}n$" and "never slower than $c_{2}n$" is telling you its exact growth behavior, which is what capacity planning needs: you can budget hardware knowing the true scaling law, not just an upper bound that might be loose by an order of magnitude.

2.11 Little o and Little Omega

Big O, big omega, and big theta are the notations we will always use. The little brothers — little o and little omega — differ from their big counterparts in exactly one character: the equals sign.

2.11.1 Strict Inequalities

The difference between big O and little o: equality is missing. Where $f(n)\in O(g(n))$ allows $f$ to have the same order of growth as $g$, $f(n)\in o(g(n))$ requires $f$ to be strictly lower than $g$ in order of growth. The professor's test question: is $n^3$ an element of little o of $n^3$? No — the equality is missing, so a function with the same order of growth is excluded. But $n^3\in O(n^3)$ — big O keeps the equality.

Mirror image: little omega requires strictly greater. $4n+6\in \omega (1)$: yes, because $4n+6$ has a strictly higher order of growth than a constant. In fact any function with growth strictly higher than constant qualifies — linear, quadratic, cubic, any of them: "constant time is the smallest order of growth, so I can have any function on the left-hand side which is greater than constant." So $4n^2+6\in \omega (1)$ works too.

2.11.2 The Limit Shortcut

For proofs — which, the professor noted, will not be asked in the exam — there is an easy shortcut that avoids thinking about the definition:

$$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=\{\begin{array}{ll}0& ⟹f(n)\in o(g(n))\\ \infty & ⟹f(n)\in \omega (g(n))\end{array}$$

Worked example: is $12n^2+6n$ in little o of $n^3$? As $n$ tends to infinity, the ratio tends to zero. Compute the ratio:

$$\underset{n\to \infty }{\lim }\frac{12n^2+6n}{n^3}=\underset{n\to \infty }{\lim }\left(\frac{12}{n}+\frac{6}{n^2}\right)=0$$

The lower-order terms do not matter — the ratio reduces to $12/n+6/n^2$, and $1/\infty$ is 0, so the limit is 0. In words: twelve n square plus six n over n cube tends to zero, so twelve n square plus six n is little o of n cube. So $12n^2+6n\in o(n^3)$. The same shortcut in the other direction proves little omega.

The professor's closing note on this topic: the limit trick is a shortcut for schoolkids — "you don't need this. You need the concept." Since big omega, big O, and big theta give you the concept, little o and little omega usually get skipped. Exam note: the limit shortcut is the fallback if a proof of little o or little omega ever appears — which, as stated, it will not.

Real-world connection: strict inequalities appear in theory-driven engineering claims — "our streaming algorithm is $o(n^2)$ per window" means it is genuinely sub-quadratic and will never degrade to quadratic, a stronger promise than $O(n^2)$; system designers use such strict guarantees when proving that a component's cost cannot dominate the pipeline.

2.12 Choosing the Right Notation

Given a computed order of growth, which of O, $\Omega$, $\Theta$ should you write? The professor's guidance is specific and exam-relevant.

2.12.1 Exact Results vs Slightly Higher or Lower

After calculating the time complexity of an algorithm, suppose the order of growth is exactly $n^3$ — just $n^3$. Then all three notations are correct: big O of $n^3$, big omega of $n^3$, and big theta of $n^3$. But the answer that earns full marks is theta of $n^3$, because it is exactly $n^3$ — theta is the exact statement.

The moment the result has something more or less than $n^3$, the choice matters:

• Result $n^3+8$ (n cube plus 8), or $n^3+3n$: the order of growth is the same, but the function sits slightly above $n^3$. Ideally, write $\Omega (n^3)$ — "this problem comes only when the power is same. Otherwise there is no confusion."
• Result $n^3-100$ (n cube minus 100): the function sits slightly below $n^3$. Write $O(n^3)$ — not theta.

In practice, textbooks and websites write big O for almost everything, because they ignore the constants and the lower-order terms; the precise $\Omega$-vs-$O$-vs-$\Theta$ choice matters only when the same highest power is involved, or when the exact notation is requested.

The class asked exactly how to make this decision, and the professor's answer is the master rule:

And a related question about whether the bounds coincide:

For $f(n)=n^3+n^2\log n$, the analysis ignores the $n^2\log n$ entirely — go with only $n^3$, and conclude "cubic". That is the bound.

2.12.2 Loose vs Tight Bounds: The Weight Analogy

When is a bound useful? The professor's analogy: the weight of a person. Suppose I say the weight of a 30-year-old person is upper bounded by 500 kg and lower bounded by 2 kg. Is that statement useful for guessing the weight? No — it is a very loose statement. Now give a tight upper bound of 60 kg and a tight lower bound of 50 kg: the weight is between fifty and sixty kilograms — now it is useful.

Map the analogy back: the lower bound is big omega, the upper bound is big O. Loose bounds — "at most 500 kg" — are technically true and practically useless. The rule: always go for the tight upper bound and the tight lower bound. That is what makes the notation informative — the professor's phrasing: "That lower bound is my big omega. And the upper bound of that 60 is my big O."

What is a bound at all? The class's answer: a bound is a limit. The professor's story to seal it — a piece of pedagogical humor worth keeping: in the epics, a circle was drawn around Sita telling her not to cross it — first credited to Rama, then corrected to Lakshman — "so from that time, bounds were there." From that story on, whenever you hear "bound", think "limit".

Real-world connection: choosing the right bound is the difference between a useful and a useless performance contract. "Our search runs in $O(n^3)$" is true but loose; "our search is $\Theta (n^2)$" (or tighter) is what a buyer needs to plan hardware, price the service, and compare vendors. Reporting tight bounds — the 50–60 kg, not the 2–500 kg — is the professional habit the whole analogy is teaching.

2.13 Correctness of an Algorithm

The last topic of the session steps back from speed to ask a deeper question: when do we even say an algorithm is correct?

2.13.1 What It Means to Be Correct

An algorithm is said to be correct if, for every input instance, it halts with the correct output. Two failure modes make an algorithm incorrect:

1. It does not halt on all input instances — there are inputs for which the algorithm never stops. This violates the finiteness property, so the algorithm is incorrect.
2. It halts with an incorrect answer on some input.

A fair question follows: can we go ahead with an incorrect algorithm? The textbook's line — which the professor flagged as debatable — says an incorrect algorithm might still be useful if we can control the error rate and it can be implemented very fast. The professor was not sure about that statement.

In this course, the stance is firm: we will not go with any incorrect algorithm. In actual work, the choice is yours — but the theory is studied on correct algorithms only.

2.13.2 Industry Correctness: Google and the Intel Pentium Bug

In industry, correctness has a different flavor: an algorithm is accepted as correct when it delivers a tangible competitive advantage. If your company makes a profit from the algorithm, if it gives an advantage over your competitors, the company goes ahead with it and calls it correct.

The contrast is the lesson: the same company calculus — "does the error hurt the business?" — produced opposite verdicts. Google's ranking is unprovably "best" in a way nobody can even define precisely, so a good-enough result wins. The Pentium division error was a specific, documentable wrong answer on a hardware product that sold in the millions, so even an astronomically small error rate was unacceptable. The difference is not the size of the error; it is whether the error is measurable, correctable, and contractually load-bearing.

The exchange that framed the whole discussion:

So the two poles: industry accepts "good enough quickly enough" when it delivers competitive advantage (Google), while a measurable, correctable failure is still a recall-level disaster (Pentium). The course itself stays with the strict definition — correct means halts with the right output on every input — and the practical lesson is left to the working world.

Real-world connection: the two poles of this section are literally the two sides of software engineering risk management. Recommendation and search systems ship with unproven optimality because their success metric (engagement, click-through, revenue) is business-defined — the "Google standard". Safety-critical systems — aircraft flight software, medical devices, financial settlement engines, chip arithmetic — must satisfy the strict standard, because their failures are measurable, provable, and catastrophic; the Pentium recall is the canonical case study taught in every hardware course for exactly this reason.

Exam Guidance Summary

Consolidated, everything the session said about exams and studying:

• Properties of an algorithm: when asked, give the five specific terms — input, output, definiteness, finiteness, effectiveness. Generic answers like "efficient" or "unambiguous" do not get credit.
• Basic operation questions: identify the single statement that executes the maximum number of times or takes the most time; never answer "the for loop" and never answer "the sum of all statements."
• Nested-loop complexity: do not write "three loops, so cubic" — that answer gets cut and earns zero marks. State the reason: one basic operation is executed this many times, so the time is $n^3$ or $n^2$. Check the loop bounds (0 to $n$ vs 1 to $n$).
• Order-of-growth comparisons: be ready for mini-comparisons like $n(n+1)+200n^2$ vs $200n^2$ (same — both quadratic), $100n^2$ vs $0.01n^3$ (the first has lower order), ${\log }_{2}n$ vs $\ln n$ (same order — change of base; textbook section 1.3.2), and $2^{n-1}$ vs $2^n$ (same order).
• Doubling-time questions: a program taking 5 seconds at input size $n$ takes 20 seconds (quadratic), 10 seconds (linear), 40 seconds (cubic) when the input doubles. If these did not click, redo them calmly by hand.
• Classification: name the class specifically (constant, logarithmic, linear, $n\log n$, quadratic, cubic, exponential, factorial). "Polynomial" is accepted as an umbrella, but specific is better. $n!$ is fine even though the textbook list omits it.
• Choosing the notation: exact $n^3$ earns full marks with $\Theta (n^3)$; $n^3+8$ is ideally $\Omega (n^3)$; $n^3-100$ is $O(n^3)$; textbooks default to big O.
• Not asked in the exam: proving the textbook's theorems (constants and lower-order terms, and the other chapter theorems) — the textbook covers them; and proofs of little o / little omega — if one ever appears, use the limit shortcut.
• Practice: 10 to 12 practice functions will be posted with solutions — attempt every one yourself before checking the solutions; go through the theorems in the textbook.
• Course logistics: an assignment will be given (not sample papers) and reading it is enough to understand; the course is running behind, so expect a fast pace next session — keep up with the material.

Key Industry Applications

• Real-world: hiring and project selection. When two people write algorithms for the same problem, the manager picks the one with the better order of growth — the entire reason asymptotic notation exists is to make that comparison professional and objective. Section 2.7's motivating story is not hypothetical: submitting two solutions with their complexity written down is the standard way candidates and teams defend their designs.
• Real-world: Google search. Google's page-ranking algorithm for its search engine is the reason Google "nailed Yahoo, Lycos, Alta Vista": it delivers a good enough result quickly enough, generates billions in pay-per-click revenue, and keeps click-through rates high — the "good enough, fast enough" standard of industry correctness from Section 2.13.
• Real-world: companies pre-decide algorithms. In established companies the algorithm is already chosen (Google has its page-ranking algorithm; the search engine is not going to change it), so the day-to-day work rarely involves re-justifying complexity. The need for this analysis appears when you design something new — which is exactly when the five-step recipe and the asymptotic comparisons of this session become the tools you use.
• Real-world: Intel Pentium bug. A hardware division failure on a tiny class of inputs forced a chip recall (widely documented as 1994) — the cautionary tale that a small, controllable error rate can still be unacceptable, and that correctness recalls are business-level events. It is the counterweight to the Google standard: measurable, documentable errors are not forgiven by "good enough."
• Real-world: plotting tools. Free online graphing tools and small Python plotting scripts make asymptotic comparisons (e.g., $2n+10$ vs $3n$) visually obvious — useful for checking your own proofs. Plotting the candidate lines and eyeballing the crossing point $n_0$ is the graphical twin of the table method.
• Real-world: bottleneck analysis. The slowest-statement rule of Section 2.4 is the principle behind production-line and web-request optimization: find the bottleneck component and fix it — speeding up the fast parts changes nothing. The basic operation is the algorithmic name for the bottleneck.
• Real-world: matrix multiplication at scale. The $n^3$ count of Section 2.5 is why graphics, neural-network training, and scientific simulation spend so much engineering on matrix libraries — doubling problem size costs 8× time, so constant-factor and exponent improvements in matrix multiply are worth real money.
• Real-world: performance contracts. Tight bounds (Section 2.12) are how vendors state guarantees: "handles $O(n)$ requests per second for $n$ servers" or "search is $\Theta (n\log n)$" — the loose 2-to-500-kg style contract is technically true and commercially useless.