complexity Complexity CYF SDC Curriculum

Learning Objectives

Quantify the memory used by different arrays

Memory consumption

Learning Objectives

Categorise algorithms as O(lg(n)), O(n), O(n^2), O(2^n)
Give practical limits to the size of inputs to O(n^2) and O(2^n) algorithms

Big-O

Learning Objectives

Explain what the significant/expensive operations for a particular algorithm are likely to be
Quantify the number of significant operations taken by a particular algorithm

“Expensive” Operations

Learning Objectives

Identify a pre-computation which will improve the complexity of an algorithm

Pre-computing