Discover How to Build Programs With Algorithms

You’ve seen that there are many different ways of creating a program. But how can you tell if your program is more efficient than another, or even if it will work at all?

To find out, you’ll need to analyze the complexity of your algorithm. You can then decide whether this level of complexity suits your needs, or compare it with other algorithms.

Algorithmic complexity is a very important concept which enables you to compare algorithms to find the most efficient one. There’s a standard notation called Big O which you can use to measure the performance of an algorithm. You’ll see how to calculate this as we go into more detail. 

But first, let me tell you a story…

Understand Exponential Complexity

Imagine you’re in the middle of a beautiful forest, enjoying a relaxing walk and minding your own business, when you suddenly see something shiny out of the corner of your eye. You walk towards it, and are astonished to find a treasure chest that looks like it could have come from a pirate ship!

You lift the chest up, and find a three-digit cast iron padlock preventing you from getting your hands on the treasure. But that’s not enough to put you off! You decide to test all the possible combinations, one after the other. 

Rather than testing each combination at random, you think about some different strategies so you don’t forget which combinations you’ve already tried. One of these is to try the smallest number possible (000), then the next (001), and so on until you reach 999. You calculate that this strategy would take you about 30 minutes, at most. 

A few minutes later, the padlock springs open! It turns out the code was 123. Easy! Your strategy worked, and you marvel at your own intelligence.

Now let’s see how we can describe this problem in pseudocode:

3_digit_padlock algorithm
Start
   For i from 0 to 9 :
      For j from 0 to 9 :
         For k from 0 to 9 :
            If code == combination :
               Stop the loops
            End If
         End For
      End For
   End For
End

In this algorithm, we have three loops going from 0 to 9, so 10 x 10 x 10 iterations—in other words 103 iterations. Using Big O notation, we can say that the time complexity of this algorithm is  $\$\backslash (O(103)\backslash )\$$ .

So, you open the chest… only to discover a second, smaller one, with a four-digit padlock. How frustrating!

Never mind, you’re feeling confident after your first success! You decide to use the same algorithm to find the code. But after an hour and half of trying, you give up. It’s probably for the best, as it would have taken you over five hours to try all the combinations!

You decide to continue your walk, taking the little chest with you, and puzzling over how adding one digit can increase the calculation time from 30 minutes to five hours.

The secret is the complexity of the algorithm. The more figures there are in the code, the longer it will take to find the answer. But what do we mean by this?

If the code has three figures, you need to test 1,000 combinations (all the numbers between 000 and 999). However, if there are four, you need to test 10,000. If there were five, you’d need to test 100,000, and so on. As you can see, our algorithm for opening the chest depends on the number of digits in the code. 

If we write the number of digits in the padlock code as  n  , the calculation time will be $\$\backslash (10^n\backslash )\$$ . Using Big O notation, we can say that the time complexity of our algorithm is   $\$\backslash (O(\; 10^n)\backslash )\$$.

This is known as exponential complexity. As you saw, the program quickly became impossible to execute, as the algorithm was too long.

Understand Linear Complexity 

After thinking long and hard, you have an idea—you decide to try a technique explained to you by your cousin Bill, who you suspect has been involved in some shady business in his time! He likes to call himself the “padlock whisperer,” and his technique is simple: he turns the dial of the first digit until he hears a click, which tells him that this digit is correct, and then he moves on to the next. This allows him to find the right digits, one by one. 

Of course, when he told you this theory, you rolled your eyes at yet another tall tale, but now you’ve spent two hours trying to open the chest, you may as well try it. What have you got to lose?

You get to work, and manage to crack the four-digit code in the space of two minutes. Hooray! You open the chest, and what's inside doesn’t disappoint.

It’s simple! Using this technique, you find the first digit of the code and then try 10 combinations. When you find the right one, you move onto the next, and try 10 more combinations, and so on for each digit.

This means that you only had to try 40 combinations (10 + 10 + 10 + 10, so 10 x 4) for this four-digit padlock. Much quicker than the 10,000 combinations you would have had to try otherwise! 

Now let’s take a look at how to write this new solution in pseudocode:

4_digit_padlock algorithm
Variable
   digit_1 ← 0 : INTEGER
   digit_2 ← 0 : INTEGER
   digit_3 ← 0 : INTEGER
   digit_4 ← 0 : INTEGER
Start
   For i from 0 to 9 :
      If it clicks :
         digit_1 ← i
      End If
   End For

   For j from 0 to 9 :
      If it clicks :
         digit_2 ← j
      End If
   End For

   For k from 0 to 9 :
      If it clicks :
         digit_3 ← k
      End If
   End For

   For m from 0 to 9 :
      If it clicks :
         digit_4 ← m
      End If
   End For
End

You test 10 combinations for each new digit of the padlock. In other words, if n is the number of digits, you test 10 x n combinations. Using Big O notation, we can say that the complexity of this algorithm is  $\$\backslash (O(10xn)\backslash )\$$. The complexity of Bill’s algorithm is a lot better than ours! 

We call this linear complexity. Why? Simply because it increases in proportion to the number of figures. 

Understand Constant Time Complexity

You decide to pay Bill a visit and show off your new padlock-unlocking skills. You’re sure he’ll be impressed!

It turns out he’s not as impressed as you hoped. “See if you can do this one, then,” he chuckles as he heaves a 500-digit padlock out of the cupboard and onto the table, which almost breaks under its weight. “You’ll need to test 5,000 combinations, and it’ll take you about three hours. Well, if you’re quick.” 

It seems you’ve encountered the same problem again—no matter how effective the technique, there are just too many digits in the padlock code. In other words, the size of the data in the problem exceeds the capacity of the algorithm.

At that moment, Bill’s son Jack walks past. He laughs, picks up a big stone, and wallops the padlock with it. Thwack! It springs open immediately. But actually… that’s a good idea…

If you think about it, his program is super effective! No matter how many digits there are, it always takes the same amount of time. Perfect!

We’re now talking about constant time complexity. This type of complexity is written as $\$\backslash (O(1)\backslash )\$$  in Big O notation.

Understand Time Complexity

If we compare our different programs, we can see that the main factor we’ve considered has been time. Our first solution took 30 minutes, whereas Jack’s only took a second!

It’s the same for every algorithm, whether it’s for sorting a list, prime factorization, or searching for the most popular course on OpenClassrooms. This is known as time complexity. 

“But what purpose does it serve?” I hear you ask. Well, it warns us if an algorithm is likely to go on forever. That’s pretty useful!

The internet provides us with a very important example of this concept in the form of food delivery websites. What happens when you search for all Chinese restaurants up to 1 km away, open until 11:00 pm, which provide home delivery? The algorithm will do its best to find search results for you. But you don’t want to wait three hours for them—you want the results page to appear in a matter of seconds. It’s therefore important for these websites to use the most efficient algorithm possible.

Understand Space Complexity

The last point you need to know about is to do with data storage. When we create an algorithm, the information is stored in the computer memory. However, this memory is not infinite. If we’re not careful, a program can quickly fill up all the free space on our computer and make it crash.

This is what’s called space complexity. The same Big O notation as for time complexity is used. 

Imagine a program where the user has to enter n elements and save them in an array. In this case, space complexity would be written as $\$\backslash (O(n)\backslash )\$$ in Big O notation, as the array will eventually contain n elements. If the algorithm uses the same n elements to create two arrays, the space complexity would then be $\$\backslash (O(2n)\backslash )\$$. 

Over to You!

Context

All throughout this course, you’ve been creating computer programs for the maze. We’re going to take a few of them and try to calculate the time and space complexity of the algorithms.

Instructions

We’re going to calculate the time and space complexity of three algorithms.

• First, this “moves” algorithm:

Moves algorithm (position_x, position_y)
Variable
   direction ← “” : STRING
Start
   direction ← enter()
   If direction == “Up” OR direction == “Down” OR direction == “Right” OR direction == “Left” :
      If direction == “Up” :
         position_y = position_y + 1
      End If
      If direction == “Down” :
         position_y = position_y - 1
      End If
      If direction == “Right” :
         position_x = position_x + 1
      End If
      If direction == “Left” :
         position_x = position_x - 1
      End If
   Else
      display “The input is not correct”
   End If
End

• We then have the following algorithm which allows us to pick up a number of keys in the maze, represented by n:

Pick_up algorithm
Variable
   player_position_x ← 0 : INTEGER
   player_position_y ← 0 : INTEGER
   end_position_x ← 5 : INTEGER
   end_position_y ← 5 : INTEGER
   keys[n] : ARRAY STRING
   moves ← 0 : INTEGER
   max_moves ← 30n : INTEGER
Start
   While player_position_x != end_position_x AND player_position_y != end_position_y AND keys.size() != n AND moves < max_moves :
      moves(player_position_x, player_position_y)
      pick_up(keys, player_position_x, player_position_y)
   End While
End

• To finish, we have the following sort algorithm:

Sort algorithm (array)
   size ← Size of array
   For i from 0 to size - 1 :
      For j from 0 to size - 1 - 1 :
         If array[j+1] < array[j] :
            swap(array[j+1], array[j])
         End If
      End For
   End For
End

Your Mission

• Work out the time and space complexity of these three algorithms:

  • moves

  • pick up

  • sort

Check Your Work

Here’s the result you should get from the exercise:

• The  moves  function:

  • Time complexity: $\$\backslash (O(1)\backslash )\$$
    The complexity is constant. There are no loops or other recursive functions.

  • Space complexity: $\$\backslash (O(1)\backslash )\$$
    The memory is not affected by this algorithm.

• The  pick up  function:

  • Time complexity: $\$\backslash (O(30n)\backslash )\$$
    The loop will iterate a maximum of 30 x n times.

  • Space complexity: $\$\backslash (O(n)\backslash )\$$

    The complexity is linear, so the array will have a maximum of n elements.

• The  sort  function:

  • Time complexity: $\$\backslash (O(n2)\backslash )\$$
    There are two nested loops which iterate n times, so there are a maximum of n x n iterations. 

  • Space complexity: $\$\backslash (O(1)\backslash )\$$
    The memory is not affected by this algorithm, as the size of the array doesn’t change.

Let’s Recap!

• The complexity of an algorithm is a measurement of the amount of time and/or space it requires.

• Time complexity is the time required to execute an algorithm, based on the input data length. 

• Space complexity measures the total amount of memory an algorithm or another operation needs to be able to run, based on the input data length. 

• Big O notation is a standard notation to describe the complexity of an algorithm. 

You’re nearly at the end—just one chapter left! Next, we’re going to look at quite an advanced concept called recursion. See you in the next chapter!