UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 7.1 Free with a free account
What Separates a Good Solution from a Poor One
Data Structures and Algorithms · Chapter 7: Measuring Algorithm EfficiencySection 7.1 · lesson 25 of 878 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: Evaluating a Solution's Speed and Memory Use →← Forward and Backward Navigation Between NodesNext lesson: Evaluating a Solution's Speed and Memory Use →
In this lesson
Judge solutions by correctness, efficiency, readability, and scalability.
- Identify the four qualities that make a solution good
- Explain why correctness must be checked before speed
- Compare how linear and quadratic solutions grow as the input size doubles
- Describe the time-memory trade-off behind many faster solutions
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,161 words). Read along, or search it.
Opening Question
Two Ways to Find Shared Birthdays
A hundred people stand in a hall. Do any two of them share a birthday? One way: take each person in turn, and ask every other person for their birthday. That's thousands of questions, and nothing else needed. Another way: hang a calendar on the wall, and ask each person to tick their date. The moment someone finds a tick already there, you have your answer. That's at most a hundred questions, plus a calendar. Both ways are right. So which one is better?
Key Idea
Four Qualities of a Good Solution
Most problems have many working solutions. When people call one good, they usually mean it does well on four separate qualities. Correctness: does it give the right answer for every valid input? Efficiency: how much time and memory does it use? Readability: can another person understand it, check it, and change it? And scalability: does it keep working well as the input grows? Fine with ten items, but painfully slow with ten thousand, is the warning sign.
Correctness
Correctness Comes Before Speed
Correctness comes first. A fast method that gives wrong answers is worse than a slow one, because no one can trust anything it says. Here's a quick shortcut for finding duplicates: it only looks at values that sit side by side. One pass, very fast. Give it three, one, three, and it answers false. The two threes aren't neighbors, so it never compares them. It only looks efficient because it skips the work it was supposed to do. So test awkward inputs first, before any talk of speed.
Readability
Clear Names Cost Nothing at Runtime
Readability is a quality too. Programs are read far more often than they're written, by teammates, and by the author, months later. One of these methods is called f. The other is called largest. Both find the biggest value. Given seventy-two, ninety-five and eighty-eight, both return ninety-five. They take exactly the same steps, and use the same memory. Only the names differ. The second can be understood at a glance, and its mistakes are far easier to spot. Readability costs nothing when the program runs.
Worked Example
Every Pair Versus a Seen Strip
Now the hall problem as code. Given an array of whole numbers from zero to nine thousand nine hundred ninety-nine, does any value appear twice? Solution one compares every value with every value after it. The counter, steps, isn't part of the answer. It just counts the comparisons. Solution two works like the calendar. It makes a strip of ten thousand true-or-false boxes, reads the numbers once, and stops at the first box already marked. Both are correct. On a few small lists, including an empty one, they always agree.
Growth
Doubling n Quadruples Pair Checks
The difference shows up as the input grows. The amount of data is called the input size, written n. With no duplicate at all, neither method can stop early. At a thousand values, solution one makes four hundred ninety-nine thousand, five hundred comparisons. Solution two makes a thousand steps. Double n to two thousand. Solution two does twice the work. Solution one does about four times as much: nearly two million. Each of the n values is compared with up to n others, so its work grows with n times n. Doubling the input doesn't double its cost. It quadruples it.
Quick Check
Comparisons for Sixteen Thousand Values
Quick check. Run solution one again, still with no duplicate, but now on sixteen thousand values. About how many comparisons does it make? Sixty-four million, a hundred twenty-eight million, or two hundred fifty-six million? Pause, and predict. About a hundred twenty-eight million: a hundred twenty-seven million, nine hundred ninety-two thousand, to be exact. Doubling n from eight thousand quadruples thirty-two million. Sixty-four million is what you'd get if the work only doubled, as it does for the seen strip. Two fifty-six would be eight times, which is what three nested loops would give.
Scalability
Faster Hardware Cannot Change Growth
That difference is invisible on small inputs. With ten values, solution one makes at most forty-five comparisons, and nobody would notice. Push the input to a million values, though, and it needs about half a trillion comparisons, while the seen strip needs a million steps. A faster computer speeds up both solutions by some fixed factor. It can't change how quickly the work grows. Staying practical as the input grows is what scalability means. And these counts describe the worst case, with no duplicate. If a duplicate sat in the first two positions, solution one would stop after one comparison. So always say which case you mean.
Trade-Offs
Spending Memory to Save Steps
So why is the seen strip so much faster? It spent memory to save steps. Its strip of ten thousand boxes is extra memory that solution one never needed. Time and memory are a solution's two main resources, and moving cost from one to the other is called a trade-off. The trade-off isn't free. If values could be any whole number up to a billion, the strip would need a billion boxes, and the fast solution would stop being practical. Everyday programs trade all the time. Storing earlier results spends memory to save steps. Compressing data spends steps to save storage.
Quick Check
Fifty Readings on a Tiny Device
One more check. A sensor sends fifty readings, and you must know whether any reading repeats. Readings can be any whole number up to two billion, and the device has very little memory. Which fits: comparing all pairs, a giant strip with one box per possible value, or is it impossible? Pause, and decide. Compare all pairs. With only fifty readings, that's at most one thousand two hundred twenty-five comparisons, which is nothing. A strip would need two billion boxes, far more than the device has. And it's far from impossible: the pair check is correct, and cheap at this size. The best solution depends on the situation: the input size, the memory available, and how often the work runs.
Vocabulary
Input Size, Steps, Time, and Space
The next lessons rely on a shared vocabulary. Input size, n, is how much data there is. A step is one small unit of work, such as one comparison. Running time is how much work a solution does, often counted in steps. Space usage is the extra memory, beyond the input.
Vocabulary
Cases and Growth Rates
The best, worst and average cases are the cheapest, the costliest, and the typical input of a given size. Growth rate is how cost increases with n. Solution two grows linearly, in step with n. Solution one is quadratic, growing with n times n.
Wrap-Up
Back to the Hall of a Hundred
Back to the hall of a hundred people. Asking every pair is solution one: no calendar, but nearly five thousand questions. The calendar is the seen strip: a hundred questions at most, paid for with a wall chart of three hundred sixty-six dates. Neither is simply the answer. With a crowd of thousands, the calendar wins easily. With three people and no wall, just ask.
Key Takeaways
What Makes a Solution Good
To sum up. A good solution is correct, efficient, readable and scalable, and correctness is the first gate. Time and memory are the two resources, and a faster solution often spends extra memory. Cost grows with n: doubling n doubled one solution's work, and quadrupled the other's. And always say which case a cost describes.
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 What Separates a Good Solution from a Poor One
What makes an algorithm good besides being correct?
What is a time-space trade-off in algorithms?
How many comparisons does checking every pair for duplicates take?
Why does a faster computer not fix a slow algorithm?
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 →