Storytelling to give comprehensible connotation to superficially deviating subjects
The Topic: Algorithmic competence is a crucial point for Data Structures-and-Algorithms class. To generalize, some algorithms work more quickly than others. For example, a sorting algorithm may work in quadratic time (O(n2)) or logarithmic time (O(log n)). The speed of determining the solution is directly dependent upon the size of the data set (e.g. size of n) and the adeptness of the algorithm.
The Story: After finishing our daily dinner my wife (Teres) and I usually give home-chores-inculcations to our children. Though the kids find it boring most of the times, my wife used to insist they spend some time learning these things one by one that it may come in handy when they grow up.
During one of those sessions we were trying to determine the best method of clearing the table, given the number of people who came to dinner; and the confines of each person who cleared the table.
Considering there are several guests at the dinner table in addition to our family though we do not know exactly how many guests; also, assuming that all diners including our family on the table have the same number of cutlery and other tableware each – tableware such as a starter dish, main dish, breads plate, side dish, dessert dish, spoons, knife, fork etcetera.
There are three alternate methods to clearing the table:
In the first alternative, one of us parents carries half of everything on the table in one trip. Then, the same person returns to the table and carries the remainder of the tableware.
In the second line of action, our eldest son moves one complete-set-of-tableware from the table to the kitchen-wash-area with each round-trip.
In the third and final approach, our youngest girl moves all sets (all set-of-tableware of each diner), omitting just the knives. She never touches the knives because she is too young. After our youngest daughter has completed her portion of the work, our elder daughter moves all of the knives in one trip from the dinner table to the kitchen sink.
Clearly, some of the methods are more effectual than the others. What is the relative efficiency of each?
The Lesson: To resolve problems the method is sure to show on the efficacy of the solution. Here in the story, the competency relied on two things: the number and size of the tableware; and the number of diners at the table. When both these values are small, efficacy doesn’t count much.
As these values elevate efficacy becomes more and more demanding or decisive.
The process of learning about efficiency is what applies to software algorithms. For outsized data-sets, efficacy is vital and unavoidable. The notation used to describe algorithmic efficacy is called O( ).
In the first action mode in the story, clearing the table is independent of the number of people or the size of tableware. That is, the algorithm for clearing the table is constant, or O(1). That means, if one of us parents has unlimited muscularity, then clearing the tableware will always take two trips.
In the second alternative, clearing the table is independent of the size and number of the tableware (called size_setting), but is reliant on the number of diners at the table (called num_people). That means, the algorithm for clearing the table with the second method is linear and dependent upon num_people. This is an O(num_people) or linear algorithm.
The third method is the most complex, and the most interesting. We already have a variable for the number of people called num_people and also a variable for the number and size of tableware with each diner, called size_setting. The third approach is dependent upon both num_people and size_setting.
How do we calculate the efficiency here?
Our youngest daughter will clear all pieces of tableware except one, which is (size_setting – 1)
The number of tableware sets is num_people. Finally, there is a single trip where our middle daughter moves all of the knives to the sink.
(num_people x (size_setting – 1)) + 1
Equation 1: Derivation of efficiency for third method.
In proper O( ) notation, small constants such as 1 are ignored. Therefore, the third approach has efficiency that is O(num_people x size_setting), or is called a quadratic algorithm.
The story explains the comparative efficacy of three different methods to the same problem.
Algorithmic efficiency is critical to writing computer software that executes quickly.