CS2004_Time_Complexity_Flashcards
(10 cards)
What is Big-O notation?
Big-O notation describes the upper bound of an algorithm’s running time as the input size grows. It tells us the worst-case time complexity.
✅ Example: Binary Search runs in O(log n), meaning time increases logarithmically with input size.
What is Big-Theta (Θ) notation?
Big-Theta notation describes a tight bound on the running time of an algorithm. It indicates both the upper and lower bounds.
✅ Example: Merge Sort is Θ(n log n), meaning it always runs in that time regardless of input.
What is Big-Omega (Ω) notation?
Big-Omega notation gives the best-case lower bound on an algorithm’s runtime — the fastest it can possibly run.
✅ Example: Insertion Sort is Ω(n) when the list is already sorted.
What does T(n) represent?
T(n) represents the exact number of primitive operations performed by an algorithm on an input of size n.
✅ Example: A nested loop might perform T(n) = n^2 + 2n + 1 operations.
How do you simplify T(n) to Big-O?
Drop all lower-order terms and constants, and keep only the highest-order term.
✅ Example: T(n) = 2n^2 + 5n + 3 → O(n^2)
What is the time complexity of a loop from i = 1 to n?
O(n) — the loop runs n times, doing constant work each time.
What is the time complexity of nested loops (two loops from 1 to n)?
O(n^2) — inner loop runs n times for each of n iterations of the outer loop.
What does O(1) mean?
O(1) means constant time — the operation takes the same amount of time regardless of input size.
✅ Example: Accessing an element in an array by index.
Give examples of logarithmic time algorithms.
Binary Search, tree operations in balanced binary search trees.
✅ Example: Searching a sorted list with Binary Search → O(log n)
What is the difference between best, worst, and average case complexity?
Best: fastest time (optimistic), Worst: slowest time (pessimistic), Average: expected performance over all inputs.
✅ Example: Quick Sort has O(n log n) average, but O(n^2) worst case.
