time complexity Flashcards
Q: List common time complexities from most to least efficient
A: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Q12: What does O(1) space complexity mean?
A12: O(1) space represents constant space complexity. The algorithm uses the same amount of memory regardless of input size. Examples include iterative algorithms that use a fixed number of variables or in-place algorithms that modify the input directly.
Q14: How does recursion affect space complexity?
A14: Recursion typically adds to space complexity due to the call stack. Each recursive call adds a new frame to the stack, storing local variables and the return address. For a recursion depth of n, this contributes O(n) to the space complexity.
Q11: What is auxiliary space?
A11: Auxiliary space is the extra space used by an algorithm during its execution, not including the space taken by the inputs. Total space complexity is the sum of auxiliary space and input space.
Q10: What does O(2ⁿ) time complexity mean?
A10: O(2ⁿ) represents exponential time complexity. The algorithm’s runtime doubles with each addition to the input size.
Q9: What does O(n²) time complexity mean?
A9: O(n²) represents quadratic time complexity. The algorithm’s runtime grows with the square of the input size. Examples include simple sorting algorithms like bubble sort, insertion sort, and selection sort, or comparing every element with every other element in a collection.
Q8: What does O(n log n) time complexity mean?
A8: O(n log n) represents linearithmic time complexity. Common in efficient sorting algorithms like mergesort, heapsort, and quicksort (average case). It’s typically seen in algorithms that break the problem into smaller parts, solve them independently, and combine the results.
Q5: What does O(1) time complexity mean?
A5: O(1) represents constant time complexity. The algorithm’s runtime remains the same regardless of the input size. Examples include accessing an array element by index or inserting at the beginning of a linked list.
Q7: What does O(n) time complexity mean?
A7: O(n) represents linear time complexity. The algorithm’s runtime grows linearly with the input size. Examples include traversing an array or a linked list, or a simple linear search.
Q7: What does O(n) time complexity mean?
A7: O(n) represents linear time complexity. The algorithm’s runtime grows linearly with the input size. Examples include traversing an array or a linked list, or a simple linear search.
Q4: What is the difference between Big O, Big Omega (Ω), and Big Theta (Θ)?
Big O (O): Upper bound - algorithm performs at most this well
Big Omega (Ω): Lower bound - algorithm performs at least this well
Big Theta (Θ): Tight bound - algorithm’s performance is bounded both above and below
Q6: What does O(log n) time complexity mean?
A6: O(log n) represents logarithmic time complexity. The algorithm’s runtime grows logarithmically as the input size increases. Each step eliminates a large portion of the input. Examples include binary search and operations on balanced binary search trees.
Q1: What is time complexity?
A1: Time complexity is a measure of the amount of computational time taken by an algorithm to run as a function of the input size. It describes how the runtime of an algorithm grows as the input size increases.
Q3: What is Big O notation?
A3: Big O notation is a mathematical notation that describes the upper bound of an algorithm’s time or space complexity in the worst-case scenario. It provides an asymptotic upper limit, representing how the algorithm scales with input size.
Q2: What is space complexity?
A2: Space complexity is a measure of the amount of memory (space) an algorithm needs as a function of the input size. It includes both the space used by the input and the auxiliary space used by the algorithm during execution.
