UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 7.2 Free with a free account
Evaluating a Solution's Speed and Memory Use
Data Structures and Algorithms · Chapter 7: Measuring Algorithm EfficiencySection 7.2 · lesson 26 of 877 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: Efficient Growth Rates →← What Separates a Good Solution from a Poor OneNext lesson: Efficient Growth Rates →
In this lesson
Measure running time, count primitive operations, and analyze extra space.
- Design a fair timing experiment with System.nanoTime, warm-up runs, and repeated trials
- Count primitive operations to express running time as a formula in n
- Distinguish the input space from the extra space a method needs
- Compare best, worst, average, and amortized cost
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 (994 words). Read along, or search it.
Opening Question
Will a Thousand Records Predict a Million
A method passes its timing test on a laptop with a thousand records. Will it still be fast enough on the real data, a million records? There are two ways to find out. An experiment runs the code, and reads the clock. An analysis counts the steps the code takes, without running it at all. Each has blind spots, so you'll want both.
Experiment
Timing Code with System.nanoTime
Java's clock for this is System dot nano time, a reading in billionths of a second. Read it before the code, read it after, and subtract. One reading isn't trustworthy. So this program throws away two warm-up runs, because Java speeds up code it sees often, then times seven more runs. It reports the median, the middle run, and the range, at three input sizes. Look at the ranges. The same work on the same data takes very different times from run to run. That's on one machine, in one moment. Yours would differ.
Limitations
What Timing Experiments Cannot Tell
Even a careful experiment has limits. Its numbers depend on the machine, and they vary from run to run. It only tests the inputs you tried, and it can't try every size. It needs finished code. And it says how long, never why. A measurement tells you what happened, once. To know what must happen, on any machine, you count.
Primitive Operations
Six n Plus Four Steps
A primitive operation is a basic step that takes a small, fixed time, whatever the data: an assignment, one arithmetic step, a comparison, or reading one array element. Here, sum array is rewritten to count its own steps. Each assignment is one, the loop test is one, the body is three, and the increment is two: an addition and an assignment. The loop test runs n plus one times, one more than the body, because the final test is the one that ends the loop. Run it: sixty-four steps for ten values, six hundred four for a hundred. That's six n plus four, a formula that's the same on every machine.
Worked Example
Counting Only the Busiest Step
Other counting conventions are possible, like counting the increment as one step. The numbers change, but how they grow with n doesn't. That's what matters. So for count pairs, count only the busiest step, the comparison. For i equals zero, the inner loop compares n minus one times, then n minus two, and so on, down to zero. That sum is n times n minus one, over two. Ten values give forty-five. Ten thousand give nearly fifty million. Doubling n multiplies that count by about four, on every machine. The noisy timed runs could only hint at that pattern.
Quick Check
An Inner Loop That Runs Three Times
Quick check, with a new loop. For each of a thousand values, this inner loop runs exactly three times. How many comparisons does it count? Pause and predict. Three thousand. The inner loop's length doesn't grow with n: it's always three. So the count is three n, which grows in step with n. Four ninety-nine five hundred would need the inner loop to run over the rest of the array. And a million would need it to run over all of it.
Space Analysis
Extra Space Beyond the Input
Memory is the second resource. The input space holds the data the method is given. The extra space is whatever the method needs on top of that. Analysis looks at the extra space, since the input is there whichever method runs. List what the method creates, and ask whether it grows with n. Reversing in place needs i, j and temp: three variables, whatever the length. Reversing into a new array needs n new slots, so its extra space grows with n. Both give five, four, three, two, one, but only one leaves the original untouched. Memory can also buy time. The seen strip, in the last lesson, spent one extra array to replace every-pair checking with a single pass. That's a time-space trade-off.
Cases
Best, Worst, and Average Search Cost
So far, every method cost the same for every input of size n. Often it doesn't. A search stops at the first match, so its cost depends on where the target is. Target in the first position: one comparison. That's the best case. Target missing: all one thousand. That's the worst case. If the target is equally likely anywhere, the average is n plus one over two: five hundred point five.
Decision Guide
Which Case Answers Which Question
Each case answers a different question. The best case is the least it can cost, which is too optimistic to plan with. The average case is the typical cost, but only if you can justify an assumption about the inputs. The worst case is the most it can cost. When you need a guarantee, like a response deadline, you use the worst case.
Amortized Cost
Bit Flips in a Binary Counter
Some operations are cheap almost every time, but occasionally expensive. Amortized cost spreads that occasional cost over the whole sequence: total cost, divided by the number of operations. A counter stored as bits shows the idea. Adding one usually flips one bit, but now and then a carry flips many. Sixteen increments flip one, two, one, three, and so on, up to five bits at once. But in all, they flip thirty-one bits: under two per increment. That's not the average case. An average needs odds about the inputs. An amortized cost needs none: it's a guarantee for the whole sequence.
Quick Check
Thirty-Two Counter Increments
One more check. The same counter now runs thirty-two increments, from zero. How many bits flip in total? Pause and predict. Sixty-three. The second sixteen increments repeat the first sixteen, except the last one, which carries through six bits instead of five. So the total is thirty-one plus thirty-two. A hundred sixty assumes every increment flips five bits, like the sixteenth. Amortized, the cost stays under two.
Key Takeaways
Measuring and Counting Cost
To sum up. A timing experiment shows what happened, once: repeat it, drop warm-up runs, and try several sizes. Counting primitive operations gives a formula in n, the same on any machine. Space analysis looks at the extra memory beyond the input. And best, average and worst cases differ, while amortized cost spreads rare expensive steps over a sequence.
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 Evaluating a Solution's Speed and Memory Use
How do you measure the running time of Java code?
What is a primitive operation in algorithm analysis?
What is the difference between average-case and amortized cost?
What is extra space in algorithm analysis?
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 →