X
(https://swayam.gov.in) (https://swayam.gov.in/nc_details/NPTEL)
[email protected]
NPTEL (https://swayam.gov.in/explorer?ncCode=NPTEL) » Data Structures and Algorithms Design (course)
Click to register for Certification exam
(https://examform.nptel.ac.in/2025_10/exam_form/dashboard)
If already registered, click to check your payment status
Course outline
About NPTEL ()
How does an NPTEL online course work? ()
Week 0 ()
Week - 1 ()
Week - 2 ()
Lecture 04: Clever Algorithms (unit?unit=26&lesson=27)
Lecture 05: Asymptotics, Fast Max-Sum Subarray (unit?unit=26&lesson=28)
Lecture 06: Local Minima in 1D (unit?unit=26&lesson=29)
Quiz: Week 2 : Assignment 2 (assessment?name=30)
Week 2 Feedback (unit?unit=26&lesson=36)
Week 2: Assignment 2 Solution (unit?unit=26&lesson=44)
Week - 3 ()
Week - 4 ()
Week 5 ()
Week 2 : Assignment 2
The due date for submitting this assignment has passed.
Due on 2025-08-06, 23:59 IST.
Assignment submitted on 2025-07-30, 11:24 IST
1) What is the worst-case time complexity of Bubble Sort? 1 point
2
O(n )
O(n log n)
O(n)
O(log n)
Yes, the answer is correct.
Score: 1
Accepted Answers:
2
O(n )
2) What is the best time complexity of the following subroutine as a 1 point
function of n? Assume each instruction takes O(1) time only.
sum = 0;
for (i = 1; i < n; i = i*2)
for(j = 0; j < i; j = j+1)
sum = sum + 1;
O(n)
O(n log n)
2
O(n )
2
O(n log n)
Yes, the answer is correct.
Score: 1
Accepted Answers:
O(n)
3) Arrange the following in increasing order of growth: O(n log n) 2 n
O(n ) O(2 ) O(n!) 1 point
2 n
O(n log n) < O(n ) < O(2 ) < O(n!)
n 2
O(n log n) < O(2 ) < O(n ) < O(n!)
2 n
O(n ) < O(n log n) < O(n!) < O(2 )
n 2
O(2 ) < O(n!) < O(n ) < O(n log n)
Yes, the answer is correct.
Score: 1
Accepted Answers:
2 n
O(n log n) < O(n ) < O(2 ) < O(n!)
4) If f (n) = n log n and g(n) = n(log n)
2
, which is true? 1 point
f (n) = o(g(n))
f (n) = ω(g(n))
f (n) = Θ(g(n))
g(n) = o(f (n))
Yes, the answer is correct.
Score: 1
Accepted Answers:
f (n) = o(g(n))
5) Let f (n) = 2
√log n
, g(n) = (log n)
5
. Which of the following is true? 1 point
g(n) = o(f (n))
f (n) = o(g(n))
f (n) = Θ(g(n))
f (n) = ω(n)
No, the answer is incorrect.
Score: 0
Accepted Answers:
g(n) = o(f (n))
6) Arrange the following functions in increasing order of asymptotic growth: 1 point
1.5
1.n
2
2.n log n
−
3.√n log n
0.75
4.n
3 < 4 < 2 < 1
2 < 3 < 4 < 1
3 < 2 < 4 < 1
4 < 3 < 2 < 1
No, the answer is incorrect.
Score: 0
Accepted Answers:
3 < 4 < 2 < 1
7) Consider the following pseudocode: 1 point
for i = 1 to n:
j=i
while j > 1:
j=j/2
What is the time complexity?
O(n log n)
O(n)
O(log n)
2
O(n )
Yes, the answer is correct.
Score: 1
Accepted Answers:
O(n log n)
8) Consider the following pseudocode: 1 point
i=2
while i <= n:
j=2
while j <= \log i:
j=j*j
i=i*2
What is the time complexity?
O(log n ⋅ log log log n)
O(log n ⋅ log log n)
O(log n)
O(n)
Yes, the answer is correct.
Score: 1
Accepted Answers:
O(log n ⋅ log log log n)
9) At each index i, the O(n) maximum subarray sum algorithm updates the running sum by: 1 point
Taking the maximum of the current element and the sum so far plus the current element
Taking the minimum of the current element and the sum so far plus the current element
Always adding the current element to the sum
Comparing the current element to the maximum sum found so far
Yes, the answer is correct.
Score: 1
Accepted Answers:
Taking the maximum of the current element and the sum so far plus the current element
10) What is the time complexity of a brute-force solution that checks all possible subarrays and computes their 1 point
sums individually?
3
O(n )
2
O(n )
O(n log n)
O(n!)
Yes, the answer is correct.
Score: 1
Accepted Answers:
3
O(n )
