0
$\begingroup$

Suppose I have a sorting algorithm that sorts a list integers. When the input size(the number of elements) $n$ is odd, it sorts using Bubble Sort and for even $n$ it uses Merge Sort. How do we perform the worst-case time complexity analysis for this algorithm?

The context in which this question came about is when I was going through the analysis of MAX-HEAPIFY algorithm given in CLRS(3rd edition) on page 154. In the worst-case analysis, the author had assumed some arbitrary input size $n$ and then concluded that the worst case occurs when the bottom-most level of the heap is exactly half full. This threw me off since in various texts and articles, $n$ is assumed to be fixed when performing the worst case analysis(and even for best or average cases for that matter) and that the number of elements at the bottom-most level of a heap of $n$ nodes is fixed. In that light, I concocted this algorithm so as to have the worst case dependent on $n$.

My intuition tells me that the worst case time complexity for this algorithm is $\mathcal O(n^2)$ since that's the worst case runtime for Bubble Sort. But I want to know the precise mathematical formulation of the worst-case time complexity analysis for any algorithm. Any insight would be much appreciated.

$\endgroup$
1
$\begingroup$

Let $f(n)$ the maximum number of elementary operations performed by the algorithm when the number of elements to sort is $n$.

An upper bound to the worst-case complexity of the algorithm is $O(n^2)$ since there exists some $n_0$ and some constant $c>0$ such that for every $n \ge n_0$, $f(n) \le c n^2$.

Moreover, given some other function $g(n) = o(n^2)$ it is false that $f(n) \in O(g(n))$ since for all $c>0$, there always exists a sufficiently large $n$ for which $f(n) \ge c g(n)$. In this sense, $O(n^2)$ is the smallest asymptotic upper bound you can hope to obtain.

Notice however that with this choice of $f(n)$ it is not true that $f(n) = \Omega(n^2)$ according to Knuth's definition of big Omega, while it is true in the Hardy–Littlewood definition. The "problem" here is that $f(n)$ is not monotonically non-decreasing, while the functions considered in algorithm analysis usually are.

Of course you can define $F(n) = \max_{0 \le n' \le n} f(n')$ to get a monotonically non-decreasing function, which is probably what you have in mind when you think of the worst-case running time of the algorithm.

Then you have: $F(n) = O(n^2)$ and $F(n)= \Omega(n^2)$ showing that $F(n) = \Theta(n^2)$.

$\endgroup$
1
  • $\begingroup$ Oh wow this cleared up a lot of confusion I had! Basically $f(n)$ will be a piece-wise function where for odd $n$, $f(n)\in O(n^2)$ and for even $n$, $f(n)\in O(n\log n).$ So overall $f(n)\in O(n^2)$. Thinking in terms of a concrete $f(n)$ rather than asymptotic class really helped me here! Thanks for such an elaborate answer! $\endgroup$ – Jamāl Jan 12 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.