Welcome to Programming and Data Structures

So what exactly is “work”? Let’s try to come up with some descriptions of how much work two different algorithms take. First, we will consider this DrawSquare algorithm:

DrawSquare of size (n):
    Pen Down
    Repeat 4 times:
        Move (n)
        Turn Clockwise (90)
    Pen Up

We might say it requires 10 “units” of work: Pen Down + 4 Moves + 4 Turns + Pen Up. Note that it doesn’t matter what size the square is (assuming Move always takes a fixed amount of time), this algorithm always requires 10 steps of work. If we decided that the pen up and pen down happen instantly and don’t count as work, then we might say the algorithm only took 8 “units” of work (4 Moves + 4 Turns); if we decided that processing the “Repeat” took one unit of work for each loop we might say that the algorithm requires 14 units (Pen Down + 4 Moves + 4 Turns + 4 Repeats + Pen Up). But whatever we decide, the problem always takes that amount of work.

Compare that to the following algorithm:

DrawShape with (n) sides:
    Pen Down
    Repeat (n) times:
        Move 100
        Turn Clockwise ( 360 / (n) )
    Pen Up

If we use it to draw a square and stick to our original accounting method, it takes 10 “units” of work. But what if use it to draw a triangle? Now it would take 8 units of work (Pen Down + 3 Moves + 3 Turns + Pen Up). If we use it to draw a pentagon it would take 12 units of work (Pen Down + 5 Moves + 5 Turns + Pen Up). A decagon would take 22 units (Pen Down + 10 Moves + 10 Turns + Pen Up). For this algorithm, the amount of work grows as the input (number of sides) grows.

If we do a little thinking, we could come up with a function relating the amount of work required f(n) to the number of sides n: f(n) = 2n + 2. Each side of the shape takes two steps, and there are two steps for putting the Pen Down and Up.

If we decided the Pen Up/Down didn’t count, we might say the function for calculating work was just f(n) = 2n. If we decided that each time we “Repeat” it costs a unit of work, each side would require three steps and the function might be f(n) = 3n + 2.

The graph below compares the work required for the two algorithms. The x-axis represents the value of n input to the algorithms while the y-axis represents f(n) - the work required.

What should be clear is that it does not matter which accounting system we use for each algorithm when comparing the two algorithms. DrawSquare remains constant regardless of \(n\text{.}\) DrawShape’s work grows in a linear fashion as \(n\) increases. No matter exactly what constants are involved in the functions that describe their work, the DrawShape algorithm has to do more work than the DrawSquare algorithm for large values of \(n\text{.}\)