Chapters 5 and 6

algorithm efficiency

Big-O Notation is a mathematical tool to measure _____

running time,

input size

Big-O Notation describes how _____ grows with _____

worst-case

Big-O Notation focuses on _____ performance

machine-specific,

scalability

Big-O Notation ignores _____ details; emphasizes _____

algorithms independently

Why use Big-O?

1. Compares _____ of hardware

performance

Why use Big-O?

2. Predicts _____ as input grows large

best algorithm

Why use Big-O?

3. Helps select the _____ for a problem

algorithm behavior

Why use Big-O?

4. Makes _____ easier to reason about

Constant Time - O(I),

Logarithmic Time - O(log n),

Linear Time - O(n),

Linearithmic Time - O(n log n),

Quadratic Time - O(n^2),

Exponential / Factorial - O(2^n), O (n!)

Common Big-O Classes (6)

Constant Time - O(I)

runtime does not grow with input size

Constant Time - O(I)

operations take the same time regardless of n

Constant Time - O(I)

examples:

• accessing an array element

• checking if a stack is empty

Logarithmic Time - O(log n)

input is repeatedly divided (often by 2)

Logarithmic Time - O(log n)

very efficient even for large inputs

Logarithmic Time - O(log n)

example:

binary search in a sorted list

Linear Time - O(n)

work grows directly with input size

Linear Time - O(n)

processes each element once

Linear Time - O(n)

example:

• finding the max value in a list

Linearithmic Time - O(n log n)

common for divide-and-conquer algorithms

Linearithmic Time - O(n log n)

faster than quadratic, slower than linear

Linearithmic Time - O(n log n)

examples:

• merge sort

• heap sort

Quadratic Time - O(n^2)

caused by nested loops

Quadratic Time - O(n^2)

work grows with the square of input size

Quadratic Time - O(n^2)

examples:

• bubble sort

• checking all pairs

Exponential - O(2^n)

work doubles for every additional element

Exponential - O(2^n)

very slow for large inputs

Exponential - O(2^n)

example:

• naive Fibonacci recursion

Factorial Time - O (n!)

grows extremely fast

Factorial Time - O (n!)

common in brute-force permutation problems

Factorial Time - O (n!)

examples:

• generating all permutations

• brute-force TSP

repeated steps,

nested repetition,

operations repeated,

divide-and-conquer,

major operations

Using Big-O for Non-Code Algorithms:

• identify _____ (loops in words)

• detect _____ (steps repeated inside steps)

• find _____ per input element

• recognize _____ descriptions

• count how many times _____ occur

count operations,

multiply,

recurrence relations,

master theorem,

best / worst / average

Using Big-O for Pseudocode / Code:

• _____ in loops

• _____ for nested loops

• apply _____ for recursion

• use _____ for divide-and-conquer

• distinguish _____ cases

growth rate

Big-O measures algorithm _____

code,

non-code

Big-O works for ______ and ______ descriptions

scalability

Big-O focuses on _____, not exact time

algorithm efficiency

Big-O helps compare _____

Omega Notation

describes a lower bound

Omega Notation

Guarantees the runtime is at least f(n)

• If an algorithm is Ω(f(n)):

• It cannot run faster than f(n)

Omega Notation

Used to highlight minimum possible performance

Theta Notation

gives a tight bound

Theta Notation

Describes the exact growth rate

Theta Notation

If an algorithm is Θ(f(n)), then:

• It does not grow faster than f(n)

• It does not grow slower than f(n)

Theta Notation

Used when best and worst cases are in the same order of magnitude

input,

Best Case, Average Case, Worst Case,

Omega, Theta, and O

Different performance Cases

• Real performance differs depending on _____

• Three perspectives: _____, _____, and _____

• These cases map well to _____, _____, and _____

Best Case

Fastest possible execution

Best Case

Minimum operations

Best Case

Represented using Ω

Average Case

Expected performance across typical inputs

Average Case

Balanced view

Average Case

Represented using Θ

Time Complexity

• is a measure of the amount of time an algorithm takes to run to completion, expressed as a function of the length of the input.

• Different Case Scenario

  • O → maximum time

  • Θ → expected time

  • Ω → minimum time

• Use all three to capture full algorithm behavior

O

maximum time

theta

expected time

omega

minimum time

overall behavior,

separate inputs,

single complexity class,

algorithm catalogs, textbooks, performance summaries

Computing for the Time complexity of the whole algorithm:

• We analyze the _____ of the algorithm

• We do not _____ into best/average/worst

• We want one _____

• Used in _____, _____, and _____

Big O notation

as the standard

runtime

Inputs vary, so _____ varies

Worst-case

describes the maximum possible cost

Big-O

• guarantees performance no matter what input is given

• This makes it the standard way to express overall complexity

Worst-case Big-O

Key Rule:

Overall complexity = _____

theta

requires tight upper and lower bounds

omega

requires a minimum guaranteed growth pattern

Θ or Ω,

O(n)

• If best/average/worst differ, then:

  • There is no single _____ for the entire algorithm

  • Only _____ remains valid.

space complexity

Measures memory usage

Variables,

Temporary structures,

Recursion depth

space complexity measures memory usage (3)

space complexity

Also has best, average, worst depending on structure

Space complexity

measures how much memory an algorithm uses during execution

Input space,

Auxiliary space,

Output space

Space complexity measures how much memory an algorithm uses during execution.

This includes (3)

Input space

Memory needed to store the input itself.

Auxiliary space

• Extra memory required by the algorithm

  • variables, data structures, stacks, buffers, recursion depth, etc.

Output space

Memory required to store the result (sometimes included, sometimes separate).

Recursion

space complexity example

Best case

Using a recursive function

• minimal recursion

Average case

Using a recursive function

• variable depth

Worst case

Using a recursive function

• deepest recursion