Is there an algorithm whose worst-case time complexity is not describable by Big-Theta?

Question

I understand the definitions of Big-O (upper bound), Big-Ω (lower bound), and Big-Θ (tight bound), particularly when it comes to its use to finding the complexity of given growth function such as f(n) = 2n2 + 12n + 30. I am looking for a concrete example of a single, specific algorithm where its worst-case time complexity is not asymptotically tight. In other words, for this algorithm, the upper bound (big Oh) for its worst-case is not equal to the lower bound (big Omega) for its worst-case, so we cannot describe its worst-case performance with a Big-Θ bound.

The algorithms that I have seen so far has same Big-O and Big-Ω in the worst case. For example, textbook often claims the complexity of insertion sort to be Θ(n2) in worst case scenario, since its big Oh and big Omega are in the same complexity class, i.e., n2.

there is already a similar question but the answer is not saisfacory:https://stackoverflow.com/questions/7628991/upper-bound-vs-lower-bound-for-worst-case-running-time-of-an-algorithm?noredirect=1&lq=1

• Siddhanth Ramakrishnan: Bogosort?
• greybeard: Hailstone? (The spelling of satisfactory isn't.)

Answer 1

A function is always at least a big-Theta of itself: the worst case time is both an upper and lower bound of itself.

$$f(n) = \Theta(f(n))$$

Maybe you're asking about algorithms that don't have a big-Theta with a "nice" expression like $\Theta(n^2)$. In that case it is easy to artificially invent such an algorithm. Given an input $n$, if $n$ is even then do nothing in $\Theta(1)$ time (or $\Theta(\log n)$ if you measure the time to read the bits of $n$). If $n$ is odd, count to 2ドル^n$. This algorithm has lower bound $\Omega(1)$ and upper bound $\mathcal{O}(2^n)$, and there is no "simple" big-Theta expression for it (at least not any involving only addition, multiplication, and exponentiation).

As for a naturally occurring example, I don't know of one off-hand, but I wouldn't be surprised there exists some.

• bilal: this sounds correct and clarifies my doubt.