algorithm-lower-bounds.md

---
title: Algorithms lower bounds
nav_order: 4
---

How can we apply the sorting lower bound to other problems in data structures and algorithms?

{% capture question %}
Consider a priority queue implementation that guarantees worst-case *Θ*(1) runtime for all methods. Without knowing anything about the optimization, give a runtime argument for why this optimization is impossible. (What does this suggest about heap sort?)
{% endcapture %}
{% include question.html question=question number=1 %}

{% capture question %}
Earlier, we learned that the problem of finding duplicates in an array reduces to sorting. If we know that comparison-based sorting algorithms must be in *Ω*(*N*log *N*), is it true that any duplicate-finding algorithm must also be in *Ω*(*N*log *N*)?
{% endcapture %}
{% capture explanation %}
A reduction to sorting is just one approach to detecting duplicates! Learning something about one algorithm for solving a problem doesn't preclude other possible algorithms.

We could alternatively use a `HashSet`. Instantiate an empty HashSet. For each element in the (unsorted) input array, first check if it is in the `HashSet`. If the element is already in the `HashSet`, return true. Otherwise, add it to the `HashSet` and continue to the next element.
{% endcapture %}
{% include question.html question=question explanation=explanation number=2 %}