# Proving tight bound Θ for worst-case running time of an algorithm without proving lower bound Ω

See this answer first: Proving worst-case running time is in $\Omega(n^2)$

Understanding the linked answer for insertion sort leads to the following statement. Prove that the statement is either incorrect or correct.

Statement: If you find $$𝑂(y)$$ for worst case running time of an algorithm using some possible worst input. This finding is sufficient to now state $$Θ(y)$$ without demonstrating $$Ω(y)$$ for worst case running time of that algorithm.

Caution:

Using insertion sort as an example - Keep in mind that when you are finding the $$y$$ in $$𝑂(y)$$ using some sample input that you know is worst, you cannot come up with $$y = 2^n$$ because you would not get $$y = 2^n$$ for any input that you can think of sorting. The worst input that you can think of is an array sorted in opposite order which will get you $$y = n^2$$. Therefore, leads to conclusion that $$O(n^2)$$ for worst case running time of insertion sort.

This conclusion is also enough to conclude $$Θ(n^2)$$ for worst case running time of insertion sort if statement given above is true. Statement is general and stated for all algorithms, not just for insertion sort as demonstrated in this example.

• I am failing to tag this user: cs.stackexchange.com/users/683/yuval-filmus
– jam
Mar 23 at 18:08
• Please upvote my question so that I can earn reputation to comment. I can't earn reputation by giving helpful answers just yet as I am new to the topics discussed here.
– jam
Mar 23 at 18:12
• You have to be a lot more specific about what you mean when you say 'you find $O(f(n))$ for worst case run time of an algorithm'. $O(f(n))$ isn't a value, or even a function; the 'most correct' way of interpreting $O(f(n))$ is as a set of functions (namely, all the functions $g(n)$ such that there are constants $M$ and $N_0$ such that $g(n) \lt Mf(n)$ for all $n\gt N_0$). From this perspective saying that a function $g$ 'is' $O(f(n))$ is a little bit of an abuse of notation; what we should say is that $g()\in O(f(n))$; that is, that $g()$ is a member of that set. Mar 24 at 4:45
• The lower bound can be found by showing each input would run through each outer loop and each inner loop no matter what you do and it is indeed quadratic. Mar 24 at 6:19
• Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.
– Community Bot
Apr 6 at 11:59

I would suggest checking exact definitions of asymptotic notations, to say informally: $$\Omega(f(n))$$ is set of functions that are lower bounded by $$f(n)$$, while $$O(f(n))$$ are set of functions upper bounded by $$f(n)$$, so when you have some example that runs in $$O(n^2)$$ it doesn't mean that it can't run in constant time, for example in $$O(1)$$, by $$O$$ you specify upper bound, not lower bound. I would suggest this Wikipedia article: https://en.wikipedia.org/wiki/Big_O_notation#The_Knuth_definition.

P.S also I don't understand how the link you provided is connected to the question you asked, the question you linked is about why 1 example input for each n is enough for proving worst-case running time of insertion sort.

• I am aware of the definitions. Few points -> 1: lets stick to insertion sort. 2: what insertion sort can do for non-worst case inputs (such as running in constant time) is irrelevant to the question. 3: to prove $Ω(n^2)$ we pick one such input of size n for which insertion sort runs in time that is function of $n^2$ and proof is done as per the linked answer. My question is why not just stick with the very worst example used to demonstrate $𝑂(𝑛^2)$ (input is array sorted in opposite order), this same example would also qualify for demonstrating $Ω(n^2)$ as per the rules of the linked answer.
– jam
Mar 23 at 20:13
• where is $O(n^2)$ mentioned in the link you provided, also opposite of the sorted order can be one example to prove worst-case running time for each n. author of the answer clarified the idea of worst-case running time and the idea that 1 such example input is enough, which input he didn't specify and wasn't necessary to specify in that answer. Mar 23 at 20:29
• I think there is only one example that can be picked to prove $O(n^2)$ and that is array sorted in opposite order. I am picking that example now. What I am asking is does that same example suffice to prove $Ω(𝑛^2)$?
– jam
Mar 23 at 21:15
• the fact that something runs in $O(n^2)$ doesn't mean that it runs in $\Omega(n^2)$ , take constant $f=O(1)$ for example which belongs to the first set but not the last one. in this case picking example you mentioned would suffice to prove $\Omega(n^2)$ however proof details may be different, since $O(n^2)$ means being upper bounded, while the $\Omega$ denotes lower bound as I've mentioned in my answer. Mar 23 at 21:18
• for the same insertion-sort, I can say that worst-case is $O(2^n)$ (am I incorrect here formally?), also if the question boils down to the question that you commented at last, I would suggest editing the post and asking exactly that question. Mar 23 at 22:15