How well does AN algorithm scale?

• Analyzing the performance of an algorithm is crucial for programmers and mathematicians. It allows us to determine if an algorithm is correct, efficient, and how well it can handle larger inputs. For example, an algorithm solving a problem for 10 cities may not work efficiently for 10,000 cities without scalability.

• A key question to ask is: How much time does our algorithm take? The exact answer can vary depending on the computer used, as different processors have different speeds for basic operations like adding two numbers.

• To address these variations, computer scientists developed a standardized method to describe time complexity: big-O notation.

Understanding Time Complexity with Big-O Notation

• Big-O notation is a mathematical way of describing how the runtime of an algorithm scales with input size. Instead of measuring exact runtimes (which depend on the machine), big-O focuses on the rate of growth of the algorithm's steps as input size increases.

• For example:

  • If an algorithm takes n steps to process an input of size n, its time complexity is O(n) (pronounced "oh-of-n").

  • If an algorithm requires a number of steps proportional to n², its runtime is O(n²).

• This notation helps generalize the "slowness" of algorithms, making it easier to compare different approaches regardless of hardware.

The Complexity of Solving TSP

• This TSP problem is very difficult to solve as you increase the number of cities (n). The number of operations that need to be performed becomes huge.

• The path-generation step is the most computationally expensive part of the algorithm.

• For n cities, the program generates n! permutations and checks them, resulting in (n−1)! × 2 unique paths.

• This gives the algorithm an O(n!) runtime, which is extremely inefficient.

• In a chart of time complexities above, O(n!) is among the worst, represented by the darkest red hue.

Try it Out Yourself activity!

• Let's demonstrate the scalability of our algorithm by experimenting the path-generation step. 

• Run this program with different lower numbers for 'numFooCities' at the very bottom of the trinket and see how the run time changes!