Big O notation

Big O notation is a mathematical concept used in computer science to describe the performance or complexity of an algorithm. It provides an upper bound on the time or space complexity of an algorithm, helping to understand how it scales with the input size. Here are some common Big O notations and what they represent:

1. O(1) - Constant Time:
   • The algorithm’s performance is constant and does not change with the size of the input data.
   • Example: Accessing an element in an array by its index.
2. O(log n) - Logarithmic Time:
   • The algorithm’s performance increases logarithmically with the input size.
   • Example: Binary search in a sorted array.
3. O(n) - Linear Time:
   • The algorithm’s performance increases linearly with the input size.
   • Example: Iterating through all elements in an array.
4. O(n log n) - Linearithmic Time:
   • The algorithm’s performance increases linearly with a logarithmic factor.
   • Example: Efficient sorting algorithms like mergesort and heapsort.
5. O(n^2) - Quadratic Time:
   • The algorithm’s performance increases quadratically with the input size.
   • Example: Simple sorting algorithms like bubble sort, insertion sort.
6. O(2^n) - Exponential Time:
   • The algorithm’s performance doubles with each addition to the input data set.
   • Example: Recursive algorithms solving the Tower of Hanoi.
7. O(n!) - Factorial Time:
   • The algorithm’s performance increases factorially with the input size.
   • Example: Algorithms that generate all permutations of an input set.