Big O Notation Examples to Know for AP Computer Science Principles

Big O Notation helps us understand how algorithms perform as input sizes grow. It categorizes execution time into different classes, from constant time to factorial time, guiding us in choosing efficient solutions for various computational problems.

1. O(1) - Constant time

   • The execution time remains constant regardless of the input size.
   • Examples include accessing an element in an array or performing a simple arithmetic operation.
   • Highly efficient and desirable in algorithm design.

2. O(log n) - Logarithmic time

   • The execution time increases logarithmically as the input size increases.
   • Commonly seen in algorithms that divide the problem in half, such as binary search.
   • Efficient for large datasets, as it reduces the number of operations significantly.

3. O(n) - Linear time

   • The execution time increases linearly with the input size.
   • Examples include iterating through an array or a list.
   • Simple and straightforward, but can become slow with very large inputs.

4. O(n log n) - Linearithmic time

   • The execution time grows in proportion to n multiplied by the logarithm of n.
   • Commonly found in efficient sorting algorithms like mergesort and heapsort.
   • Balances the need for speed and efficiency, especially with larger datasets.

5. O(n^2) - Quadratic time

   • The execution time increases quadratically as the input size increases.
   • Typical in algorithms with nested loops, such as bubble sort or selection sort.
   • Can become impractical for large datasets due to rapid growth in execution time.

6. O(2^n) - Exponential time

   • The execution time doubles with each additional element in the input size.
   • Often seen in recursive algorithms that solve problems by exploring all possibilities, like the Fibonacci sequence.
   • Generally inefficient and impractical for large inputs due to rapid growth.

7. O(n!) - Factorial time

   • The execution time grows factorially with the input size.
   • Common in algorithms that generate all permutations of a set, such as the traveling salesman problem.
   • Extremely inefficient for even moderately sized inputs, leading to impractical execution times.