Big O Flashcards
(26 cards)
What is Big O notation?
Big O notation describes the upper bound of an algorithm’s time or space complexity as input size grows, focusing on the worst-case scenario.
What does O(1) represent?
O(1) is constant time complexity, where runtime or space usage doesn’t change with input size. Example: Accessing an array element by index.
What is O(n) time complexity?
O(n) is linear time, where runtime grows proportionally with input size. Example: Looping through an array of n elements.
What does O(log n) mean?
O(log n) is logarithmic time, where runtime grows slowly as input size increases. Example: Binary search on a sorted array.
What is O(n²) time complexity?
O(n²) is quadratic time, where runtime grows with the square of input size. Example: Nested loops, like in bubble sort.
What is O(2ⁿ) time complexity?
O(2ⁿ) is exponential time, where runtime doubles with each additional input. Example: Recursive Fibonacci without memoization.
What is space complexity in Big O?
Space complexity measures the memory an algorithm uses relative to input size, including auxiliary space (e.g., temporary arrays).
What is the time complexity of accessing a hash table key?
O(1) average case for hash table lookups, assuming a good hash function and minimal collisions.
What is the time complexity of binary search?
O(log n), as it halves the search space in each step on a sorted array.
What is the worst-case time complexity of quicksort?
O(n²) in the worst case (e.g., already sorted array with poor pivot choice), but O(n log n) on average.
What is the space complexity of a recursive algorithm?
O(n) for recursive algorithms with n recursive calls on the call stack, like a recursive tree traversal.
What is the time complexity of traversing a linked list?
O(n), as you must visit each of n nodes to access or modify them.
What is the difference between O(n) and O(n log n)?
O(n) is linear, growing directly with input size; O(n log n) grows faster due to a logarithmic factor, common in efficient sorting algorithms like mergesort.
What is the time complexity of inserting into a binary search tree (BST)?
O(log n) average case for a balanced BST, but O(n) worst case for an unbalanced tree (e.g., skewed like a linked list).
Why do we drop constants in Big O notation?
Constants are dropped because Big O focuses on growth rate as input size approaches infinity. Example: O(2n) simplifies to O(n).
What is the time complexity of matrix multiplication?
O(n³) for standard matrix multiplication of two n×n matrices, due to three nested loops.
What is the space complexity of depth-first search (DFS) on a graph?
O(V) for recursive DFS, where V is the number of vertices, due to the call stack and visited set.
What is the time complexity of finding an element in a hash set?
O(1) average case, as hash sets use a hash function to locate elements quickly, assuming minimal collisions.
What does O(n!) mean, and when is it seen?
O(n!) is factorial time, growing extremely fast, seen in algorithms like solving the traveling salesman problem via brute force.
How do you determine the Big O of nested loops?
Multiply the complexities of each loop. Example: Two loops over n elements each give O(n × n) = O(n²).
What is the Big O complexity for an algorithm when (N <= 10)?
The Big O complexity for (N <= 10 ) is ( O(2^N) ) and ( O(N!) ). These represent exponential and factorial growth, common in recursive algorithms like the Towers of Hanoi or permutations, where the number of steps doubles with each ( N ) or grows factorially (O(1) lookup for small ( N ).
What is the Big O complexity for an algorithm when (N <= 100 )?
The Big O complexity for (N <= 100 ) is ( O(N^3) ). This indicates cubic growth, typical in algorithms with three nested loops, such as matrix multiplication, where runtime scales with ( N^3 ) (O(1) lookup for this range).
What is the Big O complexity for an algorithm when (N <= 10^3 ) (1000)?
The Big O complexity for (N <= 10^3 ) is ( O(N^2) ). This represents quadratic growth, common in algorithms like bubble sort or nested loops, where runtime scales with ( N^2 ) (O(1) lookup for this range).
What is the Big O complexity for an algorithm when ( N <= 10^5 ) (100,000)?
The Big O complexity for ( N <= 10^5 ) is ( O(N log N) ). This indicates linearithmic growth, typical in efficient sorting algorithms like quicksort or mergesort, balancing linear and logarithmic factors (O(1) lookup for this range).
