NEW
Font size
WorksheetsAlgorithm Complexity Quiz
Total questions: 15
Worksheet time: 5mins
If the capacity of the knapsack is 50, and we have items with weights [10, 20, 30] and values [60, 100, 120], the maximum profit using fractional knapsack is:
220
240
280
300
Time complexity of fractional knapsack using sorting is:
O(n log n)
O(n)
O(n²)
O(log n)
Huffman coding is optimal because it:
Uses dynamic programming
Uses greedy choice of minimum frequency nodes
Uses divide and conquer
Uses brute force
Time complexity of Huffman coding with priority queue is:
O(n)
O(n log n)
O(n²)
O(log n)
In maximum subarray problem, the crossing subarray is computed in:
O(1)
O(log n)
O(n)
O(n²)
In MCM, if dimensions are [10, 20, 30], the minimum multiplication cost is:
6000
12000
18000
2000
Time complexity of DP solution for MCM is:
O(n²)
O(n³)
O(n log n)
O(2ⁿ)
If we have weights [1,3,4,5], values [1,4,5,7] and capacity = 7, maximum profit in 0-1 knapsack is:
7
9
11
12
In MCM, the cost of multiplying a chain Ai...Aj at position k is given by:
cost(i,k) + cost(k+1,j) + pi−1 × pk × pj
cost(i,j) + pi−1 × pj × pk
cost(i,k) − cost(k+1,j)
cost(i,j) × (pi−1 × pk × pj)
Find the pivot element from the given input using median-of-three partitioning method. 8, 1, 4, 9, 6, 3, 5, 2, 7.
8
7
9
6
Analyze the time complexity derivation of the divide and conquer maximum subarray algorithm. Which recurrence relation represents the time complexity correctly?
T(n)=T(n−1)+O(1)
T(n)=2T(n/2)+O(n)
T(n)=T(n/2)+O(log n)
T(n)=nT(n−1)+O(n2))
Solve the following recurrence using Master's theorem. T(n) = 16T (n/4) + n
T(n) = O(n)
T(n) = O(log n)
T(n) = O(n2log n)
T(n) = O(n^2)
Solve the following recurrence using Master's theorem. T(n) = 4T (n/4) + n log n
T(n) = O(n (log n)^2)
T(n) = O(n log n)
T(n) = O(n^2 log n)
T(n) = cannot be solved using master's theorem
Given matrices A1 of dimension 10×30, A2 of dimension 30×5 and A3 of dimension 5×60,what is the cost of multiplying A1(A2A3)
4500
27000
10500
9000
Time complexity of divide & conquer maximum subarray algorithm is:
O(n)
O(n log n)
O(n²)
O(log n)
