DSA (QUIZ 7) -Greedy Algorithms and Complexity Analysis

What is the key principle of a greedy algorithm?

• Explore all possible combinations

• Always pick the global optimum

• Make the best local choice at each step

• Use recursion to reduce steps

Which of the following problems can be solved optimally using a greedy algorithm?

• 0/1 Knapsack

• Activity Selection

• Traveling Salesman

• Longest Common Subsequence

What is the greedy choice in the Coin Change Problem using denominations of 1, 5, and 10 to make 27?

• Use only 1s

• Use only 5s

• Use as many 10s, then 5s, then 1s

• Use 3 × 9 coins

Why does the Huffman coding algorithm follow the greedy approach?

• It picks the longest string first

• It chooses the lowest frequency characters first

• It tries all possible encodings

• It encodes based on the alphabet

What is a common feature of problems that work well with greedy algorithms?

• The problem requires backtracking

• The solution must be recursive

• The problem has an optimal substructure

• It needs matrix multiplication

What is the time complexity of a function that runs a single loop over a list of `n` elements?

• O(1)

• O(n)

• O(log n)

• O(n²)

Which time complexity grows the fastest as input size increases?

• O(n)

• O(log n)

• O(n log n)

• O(2n)

Binary search works efficiently because it:

• Scans the entire list

• Uses nested loops

• Reduces the search space by half

• Increases the list size

If you have a nested loop where both loops run `n` times, what is the time complexity?

• O(n)

• O(log n)

• O(n²)

• O(n³)

Which of the following best describes Big O notation?

• Best-case performance

• Average-case performance

• Worst-case performance

• Minimum input size