Quiz Space

Advanced Algorithms · End Term · 31 Aug 2025 · May 2025 term · Set QDB3

Question 15: Consider the given statements and answer the subquestion…

Question 15

+2 marksOne correct option

Consider the given statements and answer the subquestions if they are true or false.

An adversary can provide randomized quicksort with an input array of length nn that forces the algorithm to run in ω(nlg⁡n)\omega(n \lg n) time on that input.

(If you are not familiar with the ω\omega asymptotic notation, it roughly translates as “at least”. For example, we can say that it is possible to come up with an input that forces insertion sort to run for ω(n2)\omega(n^2) steps.)

  1. A

    TRUE

  2. B

    FALSE

Show answer

Correct answer

  • B

    FALSE

See the whole paperTake it as a mock test

Question 15 of 21 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 31 Aug 2025, in the May 2025 term (IIT M IMPROVEMENT FN EXAM QIA1 31 Aug 2025). It carries 2 marks.

More questions from this paper

  1. Q1In this problem you are given as input a graph T = (V, E) that is a tree (that is, T is undirected, connected, and acyc…
  2. Q2Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  3. Q3Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  4. Q4Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  5. Q5Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  6. Q6Consider the task of counting how many sequences of length n exist consisting only of numbers 0, 1, and 2 such that eac…
  7. Q7Figure question
  8. Q8Figure question
  9. Q9Choose the correct options:
  10. Q10Consider the following instance of Set Cover problem: Universe \mathcal{U} = {a, b, c} Family \mathcal{F} = {S_1 = {a, …
  11. Q11Consider the following instance of Set Cover problem: Universe \mathcal{U} = {a, b, c, d} Family \mathcal{F} = \left{S_…
  12. Q12Consider the following instance of Set Cover problem: Universe \mathcal{U} = {a, b, c, d} Family \mathcal{F} = \left{S_…
  13. Q13In the MIN-2-SAT problem, we are given a 2-CNF formula \phi and an integer k, and the objective is to decide whether th…
  14. Q14Consider the given statements and answer the subquestions if they are true or false. The worst-case running time and ex…
  15. Q16Every linear program has a unique optimal solution.
  16. Q17Recall that in the vertex cover problem, we are trying to find a smallest subset S of vertices in a graph G such that G…
  17. Q18Recall that the size of an optimal vertex cover is at most twice the size of a maximum matching of a graph G. Are there…
  18. Q19Consider the following approximation algorithm for the weighted vertex cover problem. 1: Solve the relaxed linear progr…
  19. Q20Consider the following approximation algorithm for the weighted vertex cover problem. 1: Solve the relaxed linear progr…
  20. Q21Figure question