CompSci Notes online part 1.

Overview of Complexity

• Focuses on Time Complexity (execution time) rather than code logic.

• Storage Complexity (memory usage) is a secondary consideration.

• Execution time depends on hardware; thus, efficiency is measured by the number of statement executions relative to input size $n$.

Comparing Algorithms

• Method 1 (Nested Loops): Iterates through rows and columns ($i$ and $j$). Total executions amount to $I \times J$, or $O(n^2)$ for a square matrix.

• Method 2 (Single Loop): Iterates through the diagonal once ($i = j$). Total executions amount to $I$, or $O(n)$.

Big O Notation Principles

• Definition: Predicts growth rate of runtime as input size $n$ increases.

• Rules for Calculation:

  • Focus on the highest order term (e.g., $n^2$ dominates $n$).

  • Ignore constants (e.g., $3n^2$ becomes $O(n^2)$; $n/2$ becomes $O(n)$).

  • Multiple variables must be preserved (e.g., $4m + 3n$ becomes $O(n + m)$).

Common Big O Classes

• $O(1)$ (Constant): Runtime is independent of input size.

• $O(\log n)$ (Logarithmic): Runtime increases slowly.

• $O(n)$ (Linear): Runtime increases proportionally with input.

• $O(n^2)$ (Quadratic): Runtime increases dramatically as $n$ grows.

Practical Application

• Analyzing real code allows developers to choose the most efficient algorithm based on predicted scaling behavior rather than just correctness.