Data Structures and Algorithms Flashcards

What does Big O notation describe in algorithm analysis?

Answer: An upper bound on the growth rate of an algorithm's time or space usage

Big O provides an asymptotic upper bound, describing how an algorithm's resource usage grows in the worst case.

Dynamic programming solves complex problems by:

Answer: Breaking them into overlapping subproblems and storing results to avoid recomputation

Dynamic programming uses memoization or tabulation to store subproblem results, eliminating redundant calculations.

Which algorithm design paradigm does Merge Sort follow?

Answer: Divide and Conquer

Merge Sort divides the array in half, recursively sorts each half, then merges the sorted halves together.

What is the space complexity of an algorithm that uses only a fixed number of variables regardless of input size?

Answer: O(1)

O(1) space complexity means memory usage is constant and does not grow with the input size.

Dijkstra's algorithm is used to find:

Answer: The shortest path from a source node to all other nodes

Dijkstra's algorithm computes the shortest path from a single source to every reachable vertex in a weighted graph.

The Fibonacci sequence computed recursively without memoization has which time complexity?

Answer: O(2ⁿ)

Naive recursive Fibonacci recomputes the same subproblems exponentially, resulting in O(2ⁿ) time complexity.

Which data structure enables O(1) average-case lookup, insertion, and deletion?

Answer: Hash Table

A hash table uses a hash function to map keys to array indices, enabling constant-time average operations.