UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 7.5 Free with a free account
Growth Categories and Asymptotic Bounds
Data Structures and Algorithms · Chapter 7: Measuring Algorithm EfficiencySection 7.5 · lesson 29 of 879 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Proving That an Algorithm Works Correctly →← Quadratic, Cubic, and Exponential GrowthNext lesson: Proving That an Algorithm Works Correctly →
In this lesson
Big O, Big Omega, and Big Theta bounds proved with witnesses.
- Define Big O, Big Omega, and Big Theta using the constants c and n0
- Prove a bound by choosing witnesses that make the inequality hold
- Simplify cost functions with the constant, lower-order, sum, and product rules
- Distinguish the choice of best, worst, or average case from the choice of notation
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,316 words). Read along, or search it.
Opening Question
Shape Matters More Than Constants
One method takes three n plus two steps. Another takes five n plus one. Which is better? On a faster machine, the first might be slower. And a different way of counting would change every number. What doesn't change is the shape: both double when the input doubles. Asymptotic notation records that shape, and ignores the rest.
Comparison
How Far Apart the Shapes Grow
The shapes really are different. At ten items, log n is about three, n squared is a hundred, and two to the n is a thousand twenty-four. At a hundred items, n log n is about six hundred sixty-four, n squared is ten thousand, and two to the n is about one point three times ten to the thirty. From ten items to a thousand, a hundred-fold increase, log n only triples. n grows a hundred-fold, and n squared ten thousand-fold. Two to the n leaves counting behind.
Definition
Big O and Its Witnesses
Big O says a cost grows no faster than a simple reference function, g. Precisely: f is O of g if there are constants c and n zero, with f at most c times g for every n from n zero on. The constant c allows any fixed multiple of g, so coefficients don't matter. And n zero lets the inequality fail for small inputs, so only the long run counts. To prove a bound, you name a c and an n zero that work. Those two constants are called witnesses.
Worked Example
Proving a Quadratic Bound with Witnesses
Take f of n equals three n squared, plus five n, plus two, and claim it's O of n squared. Try c equals four. At n equals four, f is seventy, and four n squared is sixty-four: too small. At five, a hundred two against a hundred. At six, a hundred forty against a hundred forty-four. From here it holds, and keeps holding. So c equals four and n zero equals six are witnesses. A table only checks a few values. The proof is algebra: n squared, minus five n, minus two, stays positive from six on. Other witnesses work too, like c equals ten, from n equals one.
Definition
Big Omega and Big Theta
Big O is only a ceiling, and a ceiling can sit far above the real cost. Big Omega gives a floor: f is at least c times g, from some n zero on. Three n squared, plus five n, plus two, is always at least three n squared, since five n plus two is never negative. A run confirms it for the first thousand values. So it's Omega of n squared, with c equals three. A function that's both O and Omega of the same g is Theta of g. Here, from n equals six on, f is trapped between three n squared and four n squared: Theta of n squared.
Key Idea
True Bounds Versus Tight Bounds
A bound can be true without being tight. Three n squared, plus five n, plus two, is also O of n cubed, and O of two to the n. It never exceeds either. Those statements are correct, but loose, and not useful. A Theta bound is always tight, so it's the most informative statement you can prove. When people say an algorithm is O of n squared, they normally mean the tightest upper bound they can prove.
Simplification Rules
Sum, Product, and Dropping Terms
Proving constants every time would be slow, so a few rules do the work. Drop constant factors: seven n is O of n. Drop lower-order terms: n squared plus fifty n plus nine is O of n squared. The sum rule: code that runs one part after another costs the larger part. A loop of n, then a loop of n squared, is O of n squared. The product rule: code repeated inside other code multiplies. N passes, each costing log n, is O of n log n. Ignore the log base. And keep separate inputs separate: a loop of n inside a loop of m is O of n times m, not n squared.
Overview
The Ladder of Growth Categories
The rules rely on a ladder of categories. Each one outgrows everything before it as n grows. Constant, from a fixed number of statements. Logarithmic, from a halving loop. Linear, one loop. Linearithmic, n log n, a loop holding a halving loop. Quadratic, two nested loops. Cubic, three. Exponential, every subset. And factorial, every ordering.
Quick Check
Tightest Bound for a Cubic Cost
Quick check. A cost works out to six n cubed, plus forty n squared, plus two n log n, plus nine hundred. What's the tightest Big O bound? Pause, and decide. O of n cubed. Six n cubed grows fastest, so the other terms drop away, and the six is a constant factor. Keeping six n cubed plus forty n squared forgets both rules. And n cubed log n multiplies terms that were only added.
Worked Example
Bounds Read from Code
To get a bound from code, count each part, combine them, keep the fastest-growing term, and drop its constant. Five methods count how often their innermost line runs. Linear gives exactly n. Two loops in a row give n plus n squared: at sixty-four, four thousand one hundred sixty. Triangular, an inner loop that runs i times, gives n times n minus one over two. At a thousand twenty-four that's about half of n squared, and half is only a constant. Halving gives three, six and ten. And n log n is n times that: ten thousand two hundred forty.
Key Rule
Take the Larger Branch
One more pattern. For an if-else, a worst-case bound takes the larger branch, because the bound must hold whichever way the test goes.
Key Idea
Cases Versus Notation
Big O is often paired with the worst case, but they're two separate choices. The case, best, worst or average, decides which cost function you're measuring. The notation, O, Omega or Theta, decides how you bound that function: from above, from below, or both. Search six values: the first item takes one comparison, the third takes three, and an absent target all six. With a thousand, two thousand or four thousand items, absent takes exactly n. So the best case is Theta of one, and the worst case is Theta of n. Big O on the worst case is a guarantee: no input of size n costs more.
Quick Check
When Quadratic Does Less Work
Quick check. Method A costs a hundred n steps. Method B costs n squared steps. So A is O of n, and B is O of n squared. For an input of eighty items, which method does less work? Pause, and decide. Method B. Eighty squared is six thousand four hundred, and a hundred times eighty is eight thousand. O of n doesn't always beat O of n squared. The notation speaks about large inputs. They tie at a hundred, and beyond that, A pulls ahead. Below it, the constants decide.
Common Mistakes
Errors When Stating a Bound
Common mistakes when stating a bound. Leaving constants and lower terms in, as in O of three n squared plus five n. Write O of n squared. Saying Big O means worst case, and Omega means best case. The notation bounds a function, and the case picks the function. Multiplying for two loops in sequence, or adding for nested ones. Sequential code adds, and nested code multiplies. And reading O of one as one step: it means bounded by a constant.
Common Mistake
Exponent Bases Cannot Be Dropped
One more trap. You may drop a constant factor, but not a number inside an exponent. Is four to the n O of two to the n? If it were, the ratio of four to the n over two to the n would stay below some constant. A run shows the ratio: about a thousand at ten, a million at twenty, a billion at thirty. The ratio is two to the n, and it grows without limit. So no c works. Exponentials with different bases are different categories.
Key Takeaways
Asymptotic Bounds Essentials
To sum up. Big O is a ceiling, Omega a floor, and Theta both: each proved by witnesses, c and n zero. Simplify by dropping constants and lower-order terms. Add for sequence, and multiply for nesting. And the case picks the function, while the notation bounds it.
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Growth Categories and Asymptotic Bounds
What is the formal definition of Big O notation?
What is the difference between Big O, Big Omega, and Big Theta?
Does Big O mean the worst case?
Is 4^n O(2^n)?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →