The Efficiency of Algorithms

Two Factors:

1. Time
   • aka: speed
2. Space

What is “Best”? \text{Complexity} = \text{Time Complexity} + \text{Space Complexity}

• We prefer fast and large programs over slow and tiny ones.
  • We can trade time for space, and vice versa.
• Analysis of Algorithms: Study of algorithm complexity.
  • The basic operation of an algorithm is the most signfiicant contributor to its total time requirement.

# A: Slow Sum Formula
# - O(n)
int sum = 0;
for (int i = 1; i <= n; i++)
  sum += i;
# B: Fast Sum Formula
# - O(1)
sum = n * (n + 1) / 2;

Professor’s Tangent:

• Q: How do you make an operation O(1)?
• A: Precompute the value and create a hash table!

Counting Basic Operations

We count the number of basic operations.

• Instead of saying “this algorithm takes n steps”, we can measure things in the order of ns.
  • e.g., “this algorithm takes O(n) steps”
  • “What happens when n is sufficiently large?”

int sum = 0;
for (int i = 1; i<=n; i++) {
  for (int j = 1; i<=n; i++) {
      sum++;
  }
}

Notation

\text{Efficiency (Best to Worst): }\\ 1 > \log n > n > n \log n > n^2 \land 2^n \land n! \\

Big O Notation: The upper bound on an algorithm’s running time.

• aka: “Worst case”
  • e.g., Doing linear search and searching the entire length of the array (n)

Big \Omega Notation: The lower bound on an algorithm’s running time.

• aka: “Best case”
  • e.g., Doing linear search and finding the thing at index 1.
• (We generally only talk about Big O notation)

Big \Theta Notation: Used when the upper and lower bound of an algorithm’s running time is the same.

• (So that we can describe \Omega and O succinctly.)

Remember: When improving algorithm efficiency, we’re concerned with improving O.