Time complexity

Question 1

Time Complexity

Answer 1

Describes how the runtime of an algorithm changes as the size of its input ($n$) grows.

Question 2

Big O Notation ($O$)

Answer 2

A mathematical notation that describes the limiting behavior (worst-case scenario) of an algorithm’s runtime as the input size ($n$) grows.

Question 3

$O(1)$ - Constant Time

Answer 3

Runtime is the same regardless of input size. \n\nPython Example: def get_first(data):\n return data[0] (Accessing an element by index)

Question 4

$O(\log n)$ - Logarithmic Time

Answer 4

Runtime grows slowly

Question 5

$O(n)$ - Linear Time

Answer 5

Runtime grows directly and proportionally with the input size ($n$). \n\nPython Example: for item in my_list:\n print(item) (Iterating through a list)

Question 6

$O(n \log n)$ - Quasilinear Time

Answer 6

A very efficient time complexity for sorting algorithms. \n\nPython Example: sorted_list = sorted(my_list) (Python’s built-in Timsort)

Question 7

$O(n^2)$ - Quadratic Time

Answer 7

Runtime grows as the square of the input size. Often involves nested loops. \n\nPython Example: for i in data:\n for j in data:\n print(i, j) (Nested iteration)

Question 8

$O(2^n)$ - Exponential Time

Answer 8

Runtime doubles with each new element added to the input. Extremely slow. \n\nPython Example: A basic recursive Fibonacci function fib(n) = fib(n-1) + fib(n-2)

Question 9

Big O Hierarchy (Fastest to Slowest)

Answer 9

$O(1) \ll O(\log n) \ll O(n) \ll O(n \log n) \ll O(n^2) \ll O(2^n)$