proving big-Oh for a function

Question

I have the following function, and I want to prove/disprove that it is $\Omega$(n$^2$):

\begin{cases} 4[sum(n/2,n)],& \text{if n is even } \\ 2n-1+sum(n-3,n), & \text{otherwise} \end{cases} (it should be 2 n-1, so a space between 2 and n)

where sum( j,k ) is a ‘partial arithmetic sum’ of the integers from j up to k, that is

\begin{cases} 0& \text{if j>k } \\ j + (j+1) + (j+2) + ... + k, & \text{otherwise} \end{cases}

e.g. sum(3,4) = 3 + 4 = 7, etc. Note that sum(j,k) = sum(1,k) – sum(1,j-1)

I tried to solve it, however have not come across one before where it has conditions...

It's same? https://math.stackexchange.com/questions/3800737/prove-disprove-big-oh/3800773#3800773 — zkutch, Aug 25 '20 at 00:32
It is simply sum of $n$ first members of arithmetic progression https://en.wikipedia.org/wiki/Arithmetic_progression — zkutch, Aug 25 '20 at 00:43
but what about the rest of the function, there are other parts too, wouldnt these parts effect the big O?¿ — thenewomp, Aug 25 '20 at 00:44
Write as answer. Look and ask, please, if you have something else unclear. — zkutch, Aug 25 '20 at 00:51
Okay I get it for big-Oh, but for big-Omega, would it not be Ω(^2)? — thenewomp, Aug 25 '20 at 01:09

zkutch · Accepted Answer · 2020-08-25T06:50:42.970

For first line you had answer from estimating sum of $n$ first members of arithmetic progression.

Second line is $2n-1$ plus member, which we already estimate. But $2n-1 \leqslant n^2$, so this member is also $O(n^2)$. Now you can use property, that $O(n^2) + O(n^2) = O(n^2)$ and you are done.

Now about $\Omega(n^2)$: For first line i.e. where is sum of $n$ first natural numbers we have $\frac{n(n+1)}{2}\geqslant \frac{n^2}{2}$, so we have definition of $\Omega$ for $N=1,C=\frac{1}{2}$. But for second line, as we have there member $2n-1$, then it is impossible to estimate it from down with multiple of $n^2$. It is possible to speak about $\Omega(n)$, so summing, about $\Theta(n)$.

proving big-Oh for a function

1 Answers1