Time Complexity Examples: Common Algorithms Explained

📚 Quick Study Guide: Time Complexity

• 📝 What is Time Complexity? It's a measure of the amount of time taken by an algorithm to run as a function of the length of the input. It helps us understand how an algorithm's runtime scales with increasing input size.
• 📈 Big O Notation ($O()$): The most common way to express time complexity. It describes the upper bound of an algorithm's growth rate, focusing on the worst-case scenario. It simplifies by ignoring constant factors and lower-order terms.
• 🔢 Common Time Complexities (from fastest to slowest growth):
  • 💡 $O(1)$ - Constant Time: The execution time is independent of the input size. E.g., accessing an element in an array by its index.
  • 🔍 $O(\log n)$ - Logarithmic Time: The execution time decreases with each step. E.g., Binary Search. The input size is halved in each step.
  • 💻 $O(n)$ - Linear Time: The execution time grows linearly with the input size. E.g., Linear Search, traversing a list.
  • 📊 $O(n \log n)$ - Linearithmic Time: Often seen in efficient sorting algorithms. E.g., Merge Sort, Quick Sort (average case), Heap Sort.
  • ⚙️ $O(n^2)$ - Quadratic Time: The execution time grows quadratically with the input size. E.g., Nested loops iterating over the entire input (Bubble Sort, Selection Sort, Insertion Sort).
  • ⚠️ $O(2^n)$ - Exponential Time: The execution time doubles with each addition to the input size. E.g., Recursive calculation of Fibonacci numbers without memoization, some brute-force algorithms.
  • 💀 $O(n!)$ - Factorial Time: The execution time grows extremely rapidly. E.g., Traveling Salesperson Problem (brute-force), permutations.
• ⭐ Best, Average, and Worst Cases:
  • ✅ Best Case: The minimum time an algorithm needs to complete.
  • 🔄 Average Case: The time an algorithm needs to complete on a typical input.
  • ⛔ Worst Case: The maximum time an algorithm needs to complete. Big O usually describes the worst case.

🧠 Practice Quiz: Time Complexity Examples

1. Which of the following algorithms has a time complexity of $O(1)$?
   A) Searching for an element in an unsorted array.
   B) Accessing an element at a specific index in an array.
   C) Traversing a linked list.
   D) Finding the maximum element in a sorted array.
2. Binary search on a sorted array typically has what time complexity in the worst case?
   A) $O(n)$
   B) $O(n^2)$
   C) $O(\log n)$
   D) $O(1)$
3. What is the time complexity of a simple linear search algorithm?
   A) $O(\log n)$
   B) $O(n)$
   C) $O(n \log n)$
   D) $O(n^2)$
4. Merge Sort and Quick Sort (average case) are examples of algorithms with which time complexity?
   A) $O(n)$
   B) $O(n^2)$
   C) $O(2^n)$
   D) $O(n \log n)$
5. A nested loop structure where the inner loop iterates from $0$ to $n-1$ for each iteration of the outer loop (also from $0$ to $n-1$) typically results in which time complexity?
   A) $O(n)$
   B) $O(n^2)$
   C) $O(n \log n)$
   D) $O(\log n)$
6. Which of the following time complexities represents the slowest growth rate (most efficient) for large input sizes $n$?
   A) $O(n^2)$
   B) $O(n)$
   C) $O(\log n)$
   D) $O(n \log n)$
7. An algorithm that calculates all possible permutations of $n$ elements will most likely have which time complexity?
   A) $O(n^2)$
   B) $O(2^n)$
   C) $O(n!)$
   D) $O(n \log n)$