UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 7.3 Free with a free account
Efficient Growth Rates
Data Structures and Algorithms · Chapter 7: Measuring Algorithm EfficiencySection 7.3 · lesson 27 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: Quadratic, Cubic, and Exponential Growth →← Evaluating a Solution's Speed and Memory UseNext lesson: Quadratic, Cubic, and Exponential Growth →
In this lesson
Constant, logarithmic, linear, and n log n growth in Java loops.
- Distinguish constant, logarithmic, linear, and n log n growth rates
- Explain why repeated halving produces logarithmic growth
- Identify the growth rate of a loop from its shape
- Predict how step counts change when the input size doubles
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,358 words). Read along, or search it.
Opening Question
Same Problem, Very Different Times
Two programs solve the same problem. On a million items, one finishes in the blink of an eye. The other takes minutes. The difference is rarely how fast the computer is. It's how the amount of work grows as the input grows. Four growth rates describe efficient algorithms: constant, logarithmic, linear, and n log n. Here's what each looks like, and the code that produces it.
Overview
Telling Rates Apart by Doubling n
Here n is the size of the input, like the number of elements in an array. The growth rate says how the number of steps changes as n changes. The shorthand keeps only the shape, and ignores fixed multipliers. Three steps per item and seven steps per item are both written O of n. Lesson seven point five makes that notation precise. To tell the four apart, double n. Constant work stays the same. Logarithmic work gains one step. Linear work doubles. And n log n a little more than doubles.
Constant Time
Steps That Ignore Input Size
Constant time means the number of steps doesn't depend on the input size. Reading one array element by index is the classic case. The computer calculates the address and fetches the value, whether the array holds ten items or ten million. First element, or last: one step either way. Asking an array for its length is constant too, since the length is stored. So is adding at the front of a linked list, or comparing two numbers.
Common Mistake
Three Misreadings of Constant Time
Three misunderstandings are common. Constant doesn't mean one step. A method that always does exactly fifty steps is still O of one. Constant doesn't mean fastest in practice, either. It means the cost won't get worse as the input grows. And a loop can still be constant. A loop that always runs five times, whatever n is, is O of one.
Linear Time
One Loop over the Input
An algorithm is linear when it handles each item a fixed number of times. The pattern is a single loop over the input. The body runs n times. Adding up the values, finding the largest, searching an unsorted array, printing every element: all linear. Double the items, and the work doubles. Two variations are still linear. A loop that jumps by a fixed amount, like i plus equals three, runs about n over three times, and the fixed divisor doesn't change the shape. And two separate loops, one after the other, do n plus n, two n steps. That's still O of n.
Logarithmic Time
Counting Halvings Down to One
Logarithmic growth is the surprising one. It grows so slowly, it almost behaves like constant time. Start with a question: how many times can you halve a number before one is left? Sixty-four halves to thirty-two, sixteen, eight, four, two, and one. Six halvings. Start from a hundred twenty-eight instead, and it takes seven. Doubling the start adds only one step. That count is the logarithm base two of n, written log two of n. Two multiplied by itself six times is sixty-four, so log two of sixty-four is six.
Worked Example
A Billion Items in Thirty Steps
Now push n up. Eight takes three halvings. A thousand takes about ten, because two multiplied by itself ten times is a thousand twenty-four. A million takes about twenty. A billion, about thirty. A thousand-fold jump in n, from a million to a billion, adds only about ten steps. That's the power of logarithmic growth.
Code Pattern
Loops That Halve or Double
In code, a loop is logarithmic when its variable is multiplied or divided by a fixed amount every pass, rather than increased by a fixed amount. This one halves m while it's above one. For a thousand, it prints nine, not ten. It stops as soon as m reaches one, and that last one is never halved. Whole halvings and the exact logarithm differ by less than one step, and the growth rate ignores that. The mirror image doubles a variable instead. i takes the values one, two, four, eight, and so on. For a thousand, it runs ten times.
Applications
Where Logarithms Appear
Logarithms appear wherever half the data is thrown away each step. A search that checks the middle of a sorted array, and drops the half without the answer, needs about log n checks. That's binary search, in lesson nine point two. Counting digits divides by ten until nothing is left: a logarithm base ten. And balanced trees keep their height logarithmic, which keeps searches short. Does the base matter? Not for the growth rate. Changing the base only multiplies by a fixed number. Halving, thirding, and dividing by ten are all written O of log n.
Quick Check
Halving Two Thousand Forty-Eight
Quick check. The halving loop runs while m is above one, and this time n is two thousand forty-eight. How many halvings does it make? Pause, and predict. Eleven. Two thousand forty-eight is two multiplied by itself eleven times, so every halving is exact, all the way down to one. Ten is the count for a thousand twenty-four, half as much. And a thousand twenty-four is only the value after the first halving, not the number of steps.
Linearithmic Time
A Halving Loop Inside a Loop
When a logarithmic job is done once for each of n items, the total is n times log n. In code, that's a loop over the input, with a halving loop inside it. Take n equals eight. The outer loop makes eight passes. Each pass halves eight down to one in three steps. So the grid has eight rows of three: twenty-four steps in all. It grows only a little faster than linear. This is the target for the efficient sorting methods later in the course. They split the data in halves, again and again, and do a linear amount of work at each level.
Comparison
The Four Rates at Large Sizes
Small inputs hide the differences: all four rates finish quickly when n is tiny. The gaps appear at large sizes. At ten items, n log n is about thirty-three steps. At a thousand, about ten thousand. At a million items, log n is about twenty steps, n is a million, and n log n is about twenty million. At a billion: thirty, a billion, and thirty billion. Picture a computer doing a billion simple steps a second. At a million items, that's twenty nanoseconds, one millisecond, and twenty milliseconds. At a billion items: a second for linear, and thirty seconds for n log n.
Experiment
Doubling Experiment Step Counts
To recognize a growth rate, run a doubling experiment: double n, and watch the step count. These counts come from running this lesson's loops. Logarithmic: each doubling adds exactly one step. Three, four, five, six. Linear: each doubling doubles the steps, eight up to sixty-four. And n log n slightly more than doubles: twenty-four, sixty-four, a hundred sixty, three eighty-four.
Pattern Guide
Reading the Rate from Loop Shape
With practice, the loop's shape tells you the rate. No loop over the input, just a fixed number of steps, is constant. A loop whose variable is multiplied or divided each pass is logarithmic. A single loop over the items, even in fixed jumps, is linear. And a loop over the input that holds a halving or doubling loop is n log n.
Quick Check
Spotting the Linearithmic Loop
One more check, with three new loops. Each counts how often its innermost line runs. Read each one carefully. What matters is how many times the innermost line runs, as n grows. Which one grows as n log n? Pause, and decide. Loop C. Its outer loop doubles i, so it makes only about log n passes. But each pass runs j over all n items. Log n passes of n steps: n log n. Loop A is nested, but its inner loop is fixed at twenty, so it's twenty n: still linear. Loop B halves, with nothing around it, so it's just logarithmic.
Key Takeaways
Four Efficient Growth Rates
To sum up. Growth rate, not raw speed, decides how a program behaves on large inputs. Constant doesn't depend on n. Logarithmic adds one step when n doubles. Linear doubles, and n log n slightly more than doubles. Logarithms come from repeated halving. And a loop holding a halving loop is n log n.
Think About It
Five Steps Versus Two Steps per Item
Something to think about. A friend says: my program does five steps per item, so it's O of five n, which is slower than your program at two steps per item. Is the notation right? Is the program really slower? What does the growth rate tell you, and what doesn't 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 Efficient Growth Rates
What does O(log n) mean in algorithms?
Does O(1) mean an operation takes one step?
How can you tell if a loop is O(n log n)?
How do you identify a growth rate with a doubling experiment?
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 →