Numerical Systems

Introduction Positional Notation Converting Between Bases Binary Addition Binary Multiplication Challenges (Python) Challenges (Java)

Modular Arithmatic

Introduction The Modulus Operator Cyphers Modular Arithmetic Modular Inverse Challenges (Java)

Algorithms

Introduction Algorithms Time Functions Asymptotic Complexity Summation Challenges

Propositional Logic

Introduction Propositional Logic Conjunction and Disjunction Implication and Equivalence Bitwise Operators Challenges

Set Theory

Introduction Sets Subsets and Supersets Set Operations Challenges

Graph Theory

Introduction Graphs Directed Graphs Structure of Language Search Trees Neural networks Game Object Trees Challenges Graph Question Generator

Proof

Introduction Proof Proof by Cases Proof by Contradiction Proof by Induction Challenges

Maths to Code

Maths to Code Challenges Question Generator

Descriptive Statistics

Introduction Statistics Measures of Central Tendency Measures of Spread Data Visualisation Correlation Challenges

Probability

Introduction Probability Basics Combinatorics Probability Trees Law of Total Probability Bayes Rule Challenges

Inferential Statistics

Introduction Probability Distributions Samples and Populations Hypothesis Testing Z Scores Student's T-Test Challenges

Time Functions

One key property we want algorithms to have is to be efficient, i.e. to use the fewest resources possible. This is most commonly considered with respect to time. But how do we work out how long an algorithm takes to run?

In this video I show how to find a time function for an algorithm.

Eleven-minute video

You can also view this video on YouTube

Key Points

Each primative operation, like adding two numbers, takes some amount of time
By adding up how many of each type of operation we need to perform, we can build up a function that expresses how long an algorithm will take
But the actual time will depend on lots of assumptions about the time taken for each primative operation.
When adding the time for loops we need to use summations. We’ll see summations in the fourth section in this topic.

Questions

1. Check your understanding

Given the time functions:

T(A) = 6n + 3
T(B) = 3n² + 2n + 1
T(C) = 3ⁿ

Work out T(A), T(B), and T(C) for values of n = 1, 2, 3, 4. Then use your answers to say which the most and least efficient function is for each value of n.

Most efficient

`n`	A	B	C
1
2
3
4

Least efficient

`n`	A	B	C
1
2
3
4

Check Answers

2. Work out time functions

Work out the time function for the following algorithms written in pseudo-code. Assume each primative operation takes t time. When you’ve got an answer, click “Show answer” to compare with my answer. If we differ slightly in what we’re counting as an operation, that’s okay.

Function arrayContains(array : N[], t : N): B
    f := false
    foreach i in array do
        if (i == t)
            f := true
    end for
    return f

line	time
2	t
3	t
4	nt
5	nt

T(arrayContains) = 2t + 2nt

Show Answers

Procedure reverseArray(a : array [0..n-1] ): N
    start := 0
    end := length(a)-1
    while (start < end) do
         tmp := a[start]
         a[start] = a[end]
         a[end] = tmp
         start++
         end--
   end while

line	time
2	t
3	2t
4	2t
5	t*(n/2)
6	t*(n/2)
7	t*(n/2)
8	t*(n/2)
9	t*(n/2)

T(reverseArray) = 5t*(n/2) + 5t

Why are we doing the loop (n/2) times? At first start and end have a difference of n. Each time through the loop, we are incremending start by 1 and decrementing end by 1. We're effectively taking steps of 2 each time instead of 1. Rather than looping n times, we are going to loop only half that.