UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 7.4 Free with a free account
Quadratic, Cubic, and Exponential Growth
Data Structures and Algorithms · Chapter 7: Measuring Algorithm EfficiencySection 7.4 · lesson 28 of 8711 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: Growth Categories and Asymptotic Bounds →← Efficient Growth RatesNext lesson: Growth Categories and Asymptotic Bounds →
In this lesson
Recognize quadratic, cubic, and exponential costs before they slow you down.
- Identify code patterns that produce quadratic, cubic, and exponential growth
- Predict how running time changes when n doubles or grows by one item
- Distinguish tractable polynomial costs from intractable exponential costs
- Spot loops hidden inside method calls and replace them with linear alternatives
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,613 words). Read along, or search it.
Opening Question
Three Shapes That Get Out of Hand
A program that handles ten items in an instant can still be useless on ten thousand. The cause isn't the computer, or the programmer. It's the shape of the cost function. Three shapes should make you pause the moment you see them: n squared, n cubed, and two to the n. For each one: what code produces it, how fast it gets out of hand, and how to spot it before a slow run tells you.
Quadratic Growth
Full Square Versus Triangle Loops
The rule is simple. If an outer loop runs n times, and for each pass an inner loop runs n times, the inner body runs n times n times. Full square visits every pair of i and j. Triangle starts j at i plus one, so it visits each pair only once: what you need to compare every item with every other. Run both. The triangle does about half the square's work: n times n minus one, over two. Yet both are quadratic. Look at the jump from a thousand to two thousand. Doubling n multiplied both columns by four. A constant like one half doesn't change that shape.
Key Rule
Not Every Nested Loop Is Quadratic
But not every pair of nested loops is quadratic. Ask how many times the inner loop runs for each pass of the outer loop. Same outer loop, four inner loops, at n equals a thousand. The full inner loop: a million. Starting at i plus one: about half a million, still quadratic. An inner loop that doubles j up to n: ten thousand. That's n log n. And an inner loop that always runs three times: three thousand, which is linear. Only an inner loop whose length grows with n makes the pair quadratic.
Quick Check
An Inner Loop That Hops by a Hundred
Quick check, with a new inner loop. It hops by a hundred at a time, and n is two thousand. How many steps does the program count? Pause, and predict. It prints forty thousand. Each outer pass runs the inner loop n over a hundred times: twenty. Two thousand passes of twenty. And that's still quadratic. The hop divides the work by a hundred, but the inner length still grows with n. At a thousand it was ten thousand: doubling n quadrupled it.
Cubic Growth
Multiplying Two Matrices
Put a third loop inside the second, and the innermost body runs n times n times n. The classic case is multiplying two n by n tables of numbers, called matrices. Every cell of the answer needs a sum of n products, and there are n times n cells. I and j choose the cell. K does its n multiplications. Multiplying these two by two tables gives nineteen, twenty-two, forty-three, fifty, after exactly eight multiplications. Then double the size, again and again: eight, sixty-four, five hundred twelve, and so on. Each doubling multiplies the work by eight.
Cubic Growth
Every Triple of Items
Cubic cost doesn't need matrices. Look at every triple of items, say to find three numbers that add up to zero, and you get three nested loops. Counting the visits gives a hundred twenty for ten items, and a hundred sixty-one thousand seven hundred for a hundred. That's about one sixth of n cubed: a smaller constant, the same shape. In general, k nested loops that each run about n times give about n to the k steps. These are polynomial costs.
Experiment
Telling Shapes Apart by Timing
You can tell these apart without reading code. Run the program at size n, then at two n, and divide the times. Linear takes about twice as long. Quadratic, four times. Cubic, eight times. Exponential is different: adding just one item doubles the time. Doubling n squares it.
Exponential Growth
Every Subset with a Bit Mask
Suppose you must choose which of n items to pack. Each item is in or out, and a complete search tries every combination: every subset. Java can walk through them with one loop, treating a whole number as a row of switches. Bit zero says if the first item is in, bit one the second, and so on. Counting mask from zero up to two to the n, minus one, visits every pattern once. One shifted left n times is two to the n. With A, B and C, that's eight subsets: empty, A, B, A B, and so on, up to all three.
Worked Example
Each Extra Item Doubles the Subsets
Each extra item doubles the number of subsets. And for each subset the inner loop looks at n bits, so the work is about n times two to the n. Five items: thirty-two subsets. Ten: a thousand twenty-four. Twenty: just over a million. Twenty-five: over thirty-three million subsets, and eight hundred thirty-eight million inner steps. From twenty to twenty-five items, the subsets multiplied by thirty-two. A quadratic algorithm, making the same jump, would grow by less than two.
Common Mistake
Base Versus Exponent
Don't mix up n squared and two to the n. In n squared, n is the base, multiplied by itself. In two to the n, n is the exponent. At ten, they're a hundred and a thousand twenty-four. At twenty, four hundred, and over a million. The second one escapes. And when order matters, it's worse. Arranging n items in a row has n factorial orderings. Ten items: three million six hundred twenty-eight thousand eight hundred. Twenty: about two point four quintillion.
Java Detail
Shift Overflow and the Long Literal
One Java detail. One shifted left by n is an int, and an int has thirty-two bits. Shift by thirty-one, and you get a negative number. Shift by thirty-two, and you get one, because Java only uses the shift distance modulo thirty-two. Use one L, a long, for larger shifts. Though by then, listing every subset is already far too slow.
Time Estimates
From Step Counts to Real Time
A step count means more as time. Assume about a billion simple steps per second. Real machines are a few times faster or slower, and that never rescues an exponential cost. At n equals twenty, n squared takes four hundred nanoseconds, and two to the n, about a millisecond. At forty, two to the n takes eighteen minutes. At sixty, thirty-six years. At a hundred, about forty trillion years. The universe is about fourteen billion years old. And n factorial at just twenty items takes seventy-seven years.
Time Budget
Largest Input for a Given Time
Flip the question. What's the largest n that fits a time budget? In one second, n squared handles about thirty-one thousand items. In an hour, almost two million. Two to the n handles twenty-nine items in a second, and only forty-one in an hour. Waiting an hour instead of a second buys twelve more items. A computer a thousand times faster makes quadratic inputs about thirty-two times larger. It adds about ten items to an exponential one, because two to the ten is about a thousand.
Quick Check
Every Subset of Thirty-Two Items
Quick check. A program tests every subset of thirty-two items, and spends one microsecond on each. About how long does it run? Pause, and predict. About seventy-two minutes. Two to the thirty-two is about four point three billion subsets. At a microsecond each, that's about four thousand three hundred seconds. And one more item, thirty-three, doubles it to almost two and a half hours.
Key Idea
Tractable Versus Intractable Costs
That's why computer scientists draw a line. Polynomial costs, like n, n log n, n squared and n cubed, are tractable: a faster machine handles clearly larger inputs. Exponential costs, like two to the n and n factorial, are intractable: usable only for small n. More hardware adds a few items. Two fine points. Polynomial isn't automatically fast: n to the tenth is polynomial, and hopeless at a thousand. And intractable doesn't mean no solution exists. The straightforward search is just too slow once n grows.
Warning Signs
Spotting Expensive Code Before Running
You can often smell an expensive algorithm before running it. A loop inside a loop over the same data means n squared. Three levels deep means n cubed. Code that builds or tests every subset or ordering is exponential. And so is giving every item an in or out choice, and exploring them all. If it's fast on ten test items but slow on real data, run the doubling test. And watch for a method call inside a loop, if the call itself loops.
Common Mistake
Loops Hidden Inside Method Calls
That last sign surprises people. Each of these snippets looks like a single loop over n items. But plus equals on a String builds a brand-new string, and copies everything built so far, every time. That's a hidden loop inside the loop. And contains walks the list from the front, every time. Both are quadratic. A StringBuilder adds in place, so its loop stays linear. Check what a call costs, not just how it looks.
Worked Example
Pair Sum from Both Ends
Seeing a warning sign is half the job. Is there a pair in a sorted array that adds up to a target? Brute force checks every pair: quadratic. The array is sorted, so a second method walks in from both ends. Sum too small? Only a bigger left value helps, so lo moves right. Too big, and hi moves left. Every step throws away one position, so it takes at most n minus one steps. Search for a target that isn't there, the worst case. At ten thousand items: about fifty million steps, against nine thousand nine hundred ninety-nine. Same answers, very different cost.
Caveat
Small Fixed Inputs Are Fine
A warning sign is a prompt to look for a better method, not a verdict. Nested loops over a chessboard's sixty-four squares, or a list of at most ten items, are fine. The danger is when n can grow.
Key Takeaways
Polynomial and Exponential Essentials
To sum up. Two nested loops whose inner length grows with n give n squared. Three give n cubed. Doubling n multiplies the cost by four, or by eight. Every subset of n items costs two to the n: each extra item doubles the work. At a billion steps a second, polynomial costs are tractable, and exponential ones are intractable beyond small n. And watch for warning signs, including loops hidden inside method calls.
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 Quadratic, Cubic, and Exponential Growth
Are two nested loops always O(n^2)?
Why is string concatenation in a loop slow in Java?
What is the difference between O(n^2) and O(2^n)?
How long does it take to check every subset of n items?
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 →