Computer Science Principles Lesson 3.17 - Algorithmic Efficiency

What Does “Algorithmic Efficiency” Mean?

  • Algorithmic efficiency is important in coding.
  • It means how fast an algorithm is and how much memory an algorithm uses.
  • More efficient = quicker and less memory used.

Example 1: Playground Speedrun

Get to the other corner of the maze using as little steps as possible. Wall collisions count as steps!

from IPython.display import display, HTML

display(HTML("""
<style>
 /* --- Container setup to center everything --- */
 .maze-demo-container {
   display: flex;
   flex-direction: column;
   align-items: center;
   justify-content: center;
   text-align: center;
   margin-top: 20px;
   margin-bottom: 20px;
 }

 /* --- Maze grid layout --- */
 .maze-demo-grid {
   display: grid;
   grid-template-columns: repeat(5, 40px);
   grid-template-rows: repeat(5, 40px);
   gap: 2px;
   margin: 10px auto;
   justify-content: center;
 }

 /* --- Each cell in the maze --- */
 .maze-demo-cell {
   width: 40px;
   height: 40px;
   background: #fff;
   border: 1px solid #ccc;
   display: flex;
   align-items: center;
   justify-content: center;
 }

 /* --- Wall cells are darker --- */
 .maze-demo-wall {
   background: #444;
 }

 /* --- Peppa's character appearance --- */
 .maze-demo-peppa {
   background: #ff69b4;
   border-radius: 50%;
   width: 30px;
   height: 30px;
 }

 /* --- Button control styling --- */
 .maze-demo-controls {
   text-align: center;
   margin-top: 10px;
 }

 .maze-demo-controls button {
   margin: 3px;
   padding: 6px 12px;
   border-radius: 6px;
   border: none;
   background: #ffb6c1;
   cursor: pointer;
   font-size: 14px;
   transition: 0.2s;
 }

 /* --- Button hover effect --- */
 .maze-demo-controls button:hover {
   background: #ff69b4;
   color: white;
 }

 /* --- Message text styling --- */
 #maze-demo-msg {
   margin-top: 10px;
   font-weight: bold;
 }
</style>

<!-- Main HTML layout for the demo -->
<div class="maze-demo-container">
 <h4>🐷 Peppa's Mini Maze Algorithm Demo</h4>

 <!-- Maze grid will be dynamically drawn here -->
 <div id="maze-demo-grid" class="maze-demo-grid"></div>
<h5 id="steps">Steps: 0</h5>

 <!-- Arrow buttons for movement -->
 <div class="maze-demo-controls">
   <button id="peppa-up">⬆️ Up</button>
   <button id="peppa-down">⬇️ Down</button>
   <button id="peppa-left">⬅️ Left</button>
   <button id="peppa-right">➡️ Right</button>
 </div>

 <!-- Message area for feedback -->
 <div id="maze-demo-msg"></div>
</div>

<script>
(function() {

 // Define the maze grid (1 = wall, 0 = open space)
 const maze = [
   [0, 0, 1, 0, 0],
   [1, 0, 1, 0, 1],
   [0, 0, 0, 0, 0],
   [0, 1, 1, 1, 0],
   [0, 0, 0, 1, 0]
 ];

 // Starting position for Peppa
 let peppa = {x:0, y:0};
 let steps = 0;

 // --- Function to draw the maze on screen ---
 function drawMaze() {
   const grid = document.getElementById('maze-demo-grid');
   if (!grid) return;
   grid.innerHTML = ''; // Clear previous maze state

   // Loop through each cell to build grid
   for (let y=0; y<5; y++) {
     for (let x=0; x<5; x++) {
       let cell = document.createElement('div');
       cell.className = 'maze-demo-cell';

       // If wall, darken cell
       if (maze[y][x] === 1) cell.classList.add('maze-demo-wall');

       // If Peppa is here, draw her
       if (peppa.x === x && peppa.y === y) {
         let peppaDiv = document.createElement('div');
         peppaDiv.className = 'maze-demo-peppa';
         cell.appendChild(peppaDiv);
       }
       grid.appendChild(cell);
     }
   }
 }

 // --- Function to check if Peppa can move ---
 function canPeppaMove(x, y) {
   // Disallow movement outside maze boundaries
   if (x < 0 || x >= 5 || y < 0 || y >= 5) return false;

   // Disallow movement into wall cells
   if (maze[y][x] === 1) return false;

   return true;
 }

 // --- Function to handle movement logic ---
 function movePeppa(dir) {
   let dx = 0, dy = 0;
             steps += 1;
             document.getElementById("steps").innerText = "Steps: " + steps;

   // Determine direction offsets
   if (dir === 'up') dy = -1;
   if (dir === 'down') dy = 1;
   if (dir === 'left') dx = -1;
   if (dir === 'right') dx = 1;

   // Calculate new coordinates
   let newX = peppa.x + dx, newY = peppa.y + dy;
   let msg = document.getElementById('maze-demo-msg');

   // Check if move is valid, then update position or warn
   if (canPeppaMove(newX, newY)) {
     peppa.x = newX; peppa.y = newY;
     msg.textContent = "✅ Peppa moved " + dir + "!";
   } else {
     msg.textContent = "❌ Can't move " + dir + " (wall or edge)!";
   }

   // Redraw maze after each move
   drawMaze();
 }

 // --- Attach button events after DOM is ready ---
 setTimeout(function() {
   document.getElementById('peppa-up').onclick = function() { movePeppa('up'); };
   document.getElementById('peppa-down').onclick = function() { movePeppa('down'); };
   document.getElementById('peppa-left').onclick = function() { movePeppa('left'); };
   document.getElementById('peppa-right').onclick = function() { movePeppa('right'); };

   // Draw the initial maze when loaded
   drawMaze();
 }, 100);

})();
</script>
"""))

🐷 Peppa's Mini Maze Algorithm Demo

Steps: 0

Example 2: Same output, different time.

These two buttons get to the same endpoint, but requre different amounts of steps to reach.

What’s So Important About Algorithmic Efficiency?

  • Processing power and time are limited.
  • Efficient algorithms finish quickly and use little RAM.
  • Inefficient algorithms can take a long time and use lots of resources.

How do We Measure Algorithmic Efficiency?

  • Algorithmic efficiency is about how much time and memory an algorithm uses.
  • Time complexity is measured using Big-O Notation.
  • Big-O Notation describes how the number of steps grows as the input size increases.
  • It helps us compare different algorithms and predict which will be faster for large inputs.
  • Big-O doesn’t give the exact number of steps, but shows how quickly work increases as problems get bigger.
  • Common Big-O examples: O(1) (constant), O(n) (linear), O(n^2) (quadratic), O(2^n) (exponential).
  • Memory usage is often related to time complexity and can also be described with Big-O.

What do these Big-O types mean?

  • O(1) Constant: The algorithm always takes the same number of steps, no matter how big the input is. Example: Checking if a number is even.
  • O(n) Linear: The number of steps grows directly with the input size. Example: Looking at every item in a list.
  • O(n²) Quadratic: The steps grow much faster—if you double the input, the work is four times as much. Example: Comparing every item in a list to every other item.
  • O(2ⁿ) Exponential: The steps double with every extra input—very quickly becomes huge! Example: Trying every possible combination in a puzzle.

Example: Designing Algorithms and Measuring Their Efficiency Using Python and Some Muddy Puddles!

Let’s create an algorithm where Peppa jumps in muddy puddles and see how algorithmically efficient it is using Big-O notation.

# Define some simple variables
jumps = 0
amount = 10

# The algorithm we'll be analyzing:
while jumps < amount:
    print("Jumping up and down in muddy puddles!")
    jumps += 1
  • The code repeats while ‘jumps’ is less than ‘amount’.
  • Each time, ‘jumps’ increases by 1.
  • The loop runs ‘amount’ times, so the computer does one extra step for each extra value of ‘amount’.
  • This is O(n) time complexity: n steps for n inputs.
  • ‘print()’ and ‘jumps += 1’ are O(1) (one step each).
  • Overall, this algorithm is O(n) time complexity.

Example: Designing Algorithms and Measuring Their Efficiency Using Javascript in Daddy Pig’s Workplace

Let’s create an algorithm to print papers on Daddy Pig’s office printer and see how algorithmically efficient it is using Big-O notation, however this time we’ll use Javascript.

%%js
// Define variables
const amount = 8;
let outerIndex = 0;
let innerIndex = 0;
let overallIndex = 0;

// The algorithm we'll be analyzing:
while (outerIndex < amount) { //Outer loop
    innerIndex = 0;
    while (innerIndex < amount) { //Inner loop
        overallIndex++;
        console.log(`Paper #${overallIndex} printing...`);
        innerIndex++;
    }
    outerIndex++;
}

<IPython.core.display.Javascript object>
  • The outer loop runs ‘amount’ times.
  • The inner loop also runs ‘amount’ times for each outer loop.
  • The whole thing runs ‘amount’ times, ‘amount’ times!
  • Outer loop: O(n), inner loop: O(n).
  • Multiply them: O(n * n) = O(n^2).
  • So, this algorithm’s time complexity is O(n^2).