Any decision tree that sorts n elements has height: - (i) \Omega(\lg n

Back to the 2019 paper

Module 1: Introduction and Complexity Analysis

20192m

Any decision tree that sorts $n$ elements has height:

(i) $\Omega(\lg n)$
(ii) $\Omega(n)$
(iii) $\Omega(n \lg n)$
(iv) $\Omega(n^2)$

This question has repeated before

Also appeared in 2022.

Search Google Ask AI

Similar questions

Design & Analysis of AlgorithmsAny decision trees that sorts n elements has height: - (i) \Omega(\lg n) - (ii) \Omega(n) - (iii) \Omega(n \lg n) - (iv) \Omega(n^2)20222m Design & Analysis of AlgorithmsThe minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is - (i) O(n) - (ii) O(\log n) - (iii) O(n \log n) - (iv) O(1)20242m Design & Analysis of AlgorithmsThe complexity of binary search algorithm is: - (i) O(n) - (ii) O(\log n) - (iii) O(n^2) - (iv) O(n \log n)20192m Design & Analysis of AlgorithmsWorst-case complexity of heap sort is - - (i) O(\log n) - (ii) O(n^2) - (iii) O(n \log n) - (iv) O(n)20242m

PreviousConsider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three? - (i) 1/8 - (ii) 1 - (iii) 8 - (iv) 8 NextAn all-pairs shortest-paths problem is efficiently solved using: - (i) Dijkstra's algorithm - (ii) Bellman-Ford algorithm - (iii) Kruskal algorithm - (iv) Floyd-Warshall algorithm

AI LearningWeb Platform

Coursify — Personal AI Course Generator

Struggling with a difficult subject or concept? Turn any engineering topic into a structured course with interactive lessons, quizzes, and research-backed explanations.

Try Coursify Free