Algorithmic Efficiency

Introduction

Algorithmic efficiency refers to the resources an algorithm uses in terms of time and space (memory). Understanding algorithmic efficiency is crucial for writing programs that perform well, especially as the size of the input grows.

Objectives

By the end of this lesson, students will be able to:

  1. Understand what algorithmic efficiency is.
  2. Analyze the time complexity of algorithms using Big O notation.
  3. Write pseudocode and Python code to demonstrate efficient algorithms.

Key Concepts

  1. Time Complexity: A measure of the amount of time an algorithm takes to complete as a function of the length of the input.
  2. Space Complexity: A measure of the amount of memory an algorithm uses as a function of the length of the input.
  3. Big O Notation: A mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

Example Syntax (College Board Pseudocode)**

College Board pseudocode uses basic constructs to represent algorithms. Here is an example of a simple loop:

FOR i ← 1 TO n
{
    // Code block to execute n times
}

`Example 1: Linear Search`

## Pseudocode
Let's write pseudocode for a linear search, which has a time complexity of O(n). This algorithm has a linear time complexity.


```python
index ← -1
FOR i ← 1 TO n
{
    IF array[i] = target
    {
        index ← i
        BREAK
    }
}
DISPLAY index

Python

Here is the equivalent Python code:

def linear_search(array, target):
    index = -1
    for i in range(len(array)):
        if array[i] == target:
            index = i
            break
    return index

array = [1, 2, 3, 4, 5]
target = 3
print(linear_search(array, target))  # Output: 2


2

Example 2: Binary Search

Pseudocode

Let’s write pseudocode for a binary search, which has a time complexity of O(log n):

left ← 0
right ← n - 1
index ← -1
WHILE left <= right
{
    mid ← (left + right) / 2
    IF array[mid] = target
    {
        index ← mid
        BREAK
    }
    ELSE IF array[mid] < target
    {
        left ← mid + 1
    }
    ELSE
    {
        right ← mid - 1
    }
}
DISPLAY index

Python

Here is the equivalent Python code:

def binary_search(array, target):
    left, right = 0, len(array) - 1
    index = -1
    while left <= right:
        mid = (left + right) // 2
        if array[mid] == target:
            index = mid
            break
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return index

array = [1, 2, 3, 4, 5]
target = 3
print(binary_search(array, target))  # Output: 2


2

Example 3 Write pseudocode to implement a bubble sort, which has a time complexity of O(n^2). This algorithm has a polynomial time complexity.

FOR i ← 0 TO n - 1
{
    FOR j ← 0 TO n - i - 1
    {
        IF array[j] > array[j + 1]
        {
            temp ← array[j]
            array[j] ← array[j + 1]
            array[j + 1] ← temp
        }
    }
}
DISPLAY array

Python

Here is the equivalent Python code:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        for j in range(0, n-i-1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

array = [5, 1, 4, 2, 8]
print(bubble_sort(array))  # Output: [1, 2, 4, 5, 8]


[1, 2, 4, 5, 8]

Example 3: Write pseudocode to implement the insertion sort algorithm, which has a time complexity of O(n²). This algorithm has a polynomial time complexity (because n is to the power of a number)

FOR i ← 1 TO n - 1
{
    key ← array[i]
    j ← i - 1
    WHILE j >= 0 AND array[j] > key
    {
        array[j + 1] ← array[j]
        j ← j - 1
    }
    array[j + 1] ← key
}
DISPLAY array

Python

Here is the equivalent Python code:

def insertion_sort(array):
    for i in range(1, len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and key < array[j]:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = key
    return array

array = [5, 1, 4, 2, 8]
print(insertion_sort(array))  # Output: [1, 2, 4, 5, 8]


[1, 2, 4, 5, 8]

Example 4: Write pseudocode to implement the fibonacci algorithm, which has a time complexity of O(2^n). This means that is an exponential algorithm.

FUNCTION Fibonacci(n)
{
    IF n <= 1
    {
        RETURN n
    }
    ELSE
    {
        RETURN Fibonacci(n-1) + Fibonacci(n-2)
    }
}
DISPLAY Fibonacci(n)

Python

Here is the equivalent Python code:

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

fibonacci(30)

832040

Time Complexity Using Python Time Module

Now that we’ve considered some basic examples, let’s play around with how long different types of algorithms take. Remember, time is just one measure of algorithmic efficiency. Collegeboard considers linear/polynomial/logarithmic to be algorithms run in reasonable time, while exponential algorithms run in unreasonable time.

import time
# Linear Search
def linear_search(array, target):
    index = -1
    for i in range(len(array)):
        if array[i] == target:
            index = i
            break
    return index

array = list(range(1, 10001))  # Large array for timing
target = 9999

start_time = time.time()
linear_search(array, target)
end_time = time.time()

print(f"Linear Search Time: {end_time - start_time} seconds")


# Binary Search

def binary_search(array, target):
    left, right = 0, len(array) - 1
    index = -1
    while left <= right:
        mid = (left + right) // 2
        if array[mid] == target:
            index = mid
            break
        elif array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return index

start_time = time.time()
binary_search(array, target)
end_time = time.time()

print(f"Binary Search Time: {end_time - start_time} seconds")


# Bubble Sort


def bubble_sort(array):
    n = len(array)
    for i in range(n):
        for j in range(0, n-i-1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

array = [5, 1, 4, 2, 8]

start_time = time.time()
bubble_sort(array)
end_time = time.time()

print(f"Bubble Sort Time: {end_time - start_time} seconds")

# Fibonnaci

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

n = 30  # Choosing a smaller n for timing

start_time = time.time()
fibonacci(n)
end_time = time.time()

print(f"Fibonacci (Exponential) Time: {end_time - start_time} seconds")







Linear Search Time: 0.0003268718719482422 seconds
Binary Search Time: 3.719329833984375e-05 seconds
Bubble Sort Time: 3.1948089599609375e-05 seconds
Fibonacci (Exponential) Time: 0.230820894241333 seconds

Hacks

Review each of the sections above and produce …

  • Write pseudocode and Python code to implement and time an insertion sort algorithm.
  • Compare the performance of insertion sort (O(n^2)) with bubble sort (O(n^2)) for different sizes of input arrays.