Introduction to Big O Notation

Big O Notation is a method to describe an algorithm's performance relative to its input size. It indicates how fast an algorithm runs or how much memory it uses. Performance is primarily measured in time and sometimes memory space, with this course focusing mainly on time complexity.

Using the example of linear search, the number of comparisons is directly proportional to the input size. For 'n' items, there are 'n' comparisons. This direct relationship means the running time of linear search is Big O(n), signifying linear growth: as input size increases, the number of operations increases at the same rate.

The linear growth of an algorithm described by Big O(n) can be visualized with a graph. The x-axis represents the number of items (input size), and the y-axis represents the number of comparisons. The plot shows a linear increase: 10 items require 10 comparisons, 100 items require 100 comparisons, and so on. This demonstrates that operations increase at the same rate as input size.

Crucially, Big O Notation does not measure speed in seconds. Instead, it quantifies the number of operations an algorithm performs. Therefore, when describing running time with Big O Notation, like Big O(n), 'n' refers to the number of operations, not an exact time duration. It provides a way to compare the efficiency of algorithms based on their operational growth.