Big O Notation and Classification of Algorithms (AQA A-Level Computer Science): Flashcards

Set of instructions that performs a specific task

Method to describe time/space complexity of algorithms

How long an algorithm takes to run

Constant time - same execution time regardless of input size

Linear time - runtime proportional to input size

Polynomial time - runtime proportional to square of input

Logarithmic time - e.g., binary search splits data repeatedly

Problem solvable in polynomial time

Theoretically solvable but not in polynomial time

Provides approximate solution to intractable problems