WorksheetsDSA (QUIZ 7) -Greedy Algorithms and Complexity Analysis
Total questions: 15
Worksheet time: 8mins
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
What does space complexity measure?
Execution time
Number of loops
Memory used during execution
Number of variables in source code
What is the space complexity of this function?
O(n)
O(n²)
O(1)
O(log n)
Which type of algorithm typically uses more space due to the call stack?
Iterative
Sorting
Recursive
Greedy
If an algorithm creates a new array of the same size as the input array, what is the space complexity?
O(1)
O(n)
O(log n)
O(n²)
Which function has a quadratic space complexity?
Loop that sums numbers
Function that creates all pairs from a list
Single loop with one variable
Accessing an element from an array
