749 views

Consider two statements below -

• $\text{S1}:$ For all positive $f(n), f(n) + o(f(n)) = \theta(f(n)).$
• $\text{S2}:$ For all positive $f(n), g(n)$ and $h(n),$ if $f(n) = O(g(n))$ and $f(n) = \Omega(h(n)),$ then $g(n) + h(n) = \Omega(f(n))$

Which of the following is the correct option.

1. $\text{S1}$ is True but $\text{S2}$ is False.
2. $\text{S2}$ is True but $\text{S1}$ is False.
3. Both are True.
4. Both are False.

Tbh everything that has been taught in class is enough to solve this.

When you write f(n) + o(f(n)), this o(f(n)) cannot be a set of functions (common sense), so it must be an element which belongs to set o(f(n)).

For formal definitions and terms read "Asymptotic notation in equations and equalities" from CLRS, it's from chapter 3, as mentioned by {ankitgupta}.
If that's the case then writing

o(f(n)) is strictly less than f(n) is a valid statement

but ankitgupta said we cant write like that

this is the issue

@jiren, I wanted to make things correct. It’s upto you or anyone whether they believe it or not on a good book. And This book is written by Turing award winner which is considered as the Nobel prize of computer science.

You are believing that asymptotic analysis means $n \geq n_0$ or it is for sufficiently large $n$ which is not completely true.

There are books which have written on this single topic. Anyone can read about How these asymptotic notations came into picture, why we use $n \geq n_0$ or $n \leq n_0$ etc if they get free time.

Answer is option C  which is both statements are correct

edited

If anyone had doubt on how i wrote

o(f(n)) is strictly less than f(n)

here is the reason

See

let h(n) = o(f(n))

it means h(n) < c*f(n)

If I ignore the constant for simplicity

h(n) < f(n)

We can replace h(n) with o(f(n))

means o(f(n) < f(n)

so i wrote o(f(n)) is strictly less than f(n)

For convenience let’s take an example

“ o(f(n)) will be strictly less than f(n) “, how? Isn’t o(f(n)) strictly greater than f(n)?
Bro i wrote the explanation 20 hrs back

may be u missed that 😋
In s2 before the last line i think that would be g(n) is greater equal to f(n)
edited
yes correct

it was a typo

i meant to write g(n) >= f(n)
edited by

I understood it this way. o(---) is a set of functions stricly less than ---

o(f(n)) is just a notation

to be precise u should write h(n) belongs to

other than that remaining is correct
Ok, thanks. I will correct it. :)
Writing statement “$o(f(n))$ will be strictly less than $f(n)$” is technically incorrect.

what does the meaning of writing a set of functions is less than a particular function ?

The given statement means $o(f(n)) \in o(f(n))$.

Can a set belongs to itself ? ( Russell’s Paradox ? )

If we write: $f(n) + o(f(n)) = \Theta (f(n))$

It means for “any” function $g(n) \in o(f(n)),$ there is “some” function $h(n) \in \Theta(f(n))$ such that

$f(n) + g(n) = h(n)$ for all $n.$

So, here, we need to say, suppose, $g(n) \in o(f(n))$ then $f(n) + g(n) \in \Theta (f(n))$ and “any” function $g(n)$ which is in $o(f(n))$ is strictly smaller than $f(n).$

Since, you have not used “exists” and “all” words with constant ‘c’ for little-oh and Big-Oh, I hope you know when to use which word.

(Mentioned all these things because you have mentioned the above statement at least 3 times and very less probability that it is typo.)
I think u didn't saw the comment that I posted

in that i clearly mentioned that o(f(n)) is to be replaced by h(n) as i had written h(n) = o(f(n))

when i was using o(f(n)) anywhere I was literally  talking about h(n) and h(n) can be anything which is strictly less than f(n)

u r talking about set of functions and i was talking about a single function

since h(n) is a function i can compare two functions right

Also when we say h(n) = o(f(n)) sir already said that we are abusing the belongs to

Abusing the notation is fine but it should not lose its meaning. Writing $o(f(n)) < f(n)$ or $o(f(n)) = o(f(n))$ is incorrect.

When we go too deep i think some terms cant even make sense like

In $f(n) + o(f(n)) = \Theta(f(n)),$ writing $f(n) + o(f(n))$ is perfectly valid. Here, $o(f(n))$ and $\Theta(f(n))$ are still functions which are called “anonymous functions”, they are not interpreted as a set of functions for the given equation. You can say, they are defined or interpreted like that when asymptotic notations come in equations or inequalities. It is already mentioned it in my first comment.

Read section “Asymptotic notation in equations and inequalities”  in Chapter $3$ from CLRS.

If o(f(n)) is treated as a function when it is present in equation and inequalities

then what's wrong in saying o(f(n)) <  f(n)

because the above is inequality so here also o(f(n)) should be treated as anonymous function

so the inequality is valid according to your reasoning i guess
Suppose, inequality is true and you are correct.

So, $o(f(n)) < f(n)$ is true where let any function $g(n) \in o(f(n))$ such that $g(n) < f(n)$

And here, $g(n) \in o(f(n))$ means $g(n) > f(n)$

Can you please tell me any $f$ and $g$ such $g<f$ and $g>f$ at the same time ?
edited
If g(n) = o(f(n)) then how come g(n) > f(n)

i didnt get it

g(n)∈o(f(n)) means 𝑔(𝑛)>𝑓(𝑛)  This line

Also u r the one who said in an inequality

o(f(n)) should be treated as a function

Now u r taking it as a set of functions

Which convention are you following ??

Set of functions OR anonymous function
If you write $g(n) = o(f(n))$ then for some $n,$ you can have $g(n) > f(n).$

For example, $f(n) = n^2$ and $g(n) = 10n.$ Here we have $g(n) = o(f(n))$ but $g(2) > f(2)$

And if you see the interpretation given in CLRS, we have to consider all $n.$ i.e.

$o(f(n)) < f(n)$ is true when any function $g(n) \in o(f(n))$ such that $g(n) < f(n)$ for all $n$ as in the case of equation.

So, if you take $f(n) = n^2$ and $g(n)=10n$ then $10n \in o(n^2)$ and $10n < n^2$ should hold for all $n$ but for $n=2$ it does not hold.

You might loosely say $o(f) < f.$
edited

But according to formal definition it should not be “FOR ALL N” it should be

“FOR ALL N >= N0” and we can take N0 as 1000 now 10n = o(n^2)

Also see this

We are talking about these functions asymptotically so we can say that

For reference sachin sir said this

question reference is

Have you checked the section mentioned in this comment ?

Yeah we are discussing about that comment only

what do you want to convey??

There are two things which I wanted to convey. Summarising below (most of the things here are copied from the above comments):

Assuming $f$ and $g$ are positive functions,

$1)$ If we write: $f(n) + o(f(n)) = \Theta (f(n))$

It means for “any” function $g(n) \in o(f(n)),$ there is “some” function $h(n) \in \Theta(f(n))$ such that

$f(n) + g(n) = h(n)$ for all $n.$

(Remember this equation should be true for all $n,$ not only for large $n.$)

(Now, based on this, we should have to write things for first statement.)

$2)$ If we write $o(f(n)) < f(n),$ it means for any function $g(n) \in o(f(n))$ such that $g(n) < f(n)$ for all $n.$

(As in case of equation, this inequality should also be true for all $n.$)

If we write $g(n) = o(f(n))$ then for some $n,$ you can have $g(n) > f(n).$ and since, we should have $g(n) < f(n)$ So, this statement might not be correct for all positive functions $f(n)$ because inequality may not hold for all $n.$

For example, $f(n) = n^2$ and $g(n) = 10n.$ Here we have $g(n) = o(f(n))$ but $g(2) > f(2)$

So, $10n \in o(n^2)$ and $10n < n^2$ should hold for all $n$ but for $n=2$ it does not hold.

We might loosely say $o(f) < f.$

section “Asymptotic notation in equations and inequalities”  in Chapter 3

section 2.5

We are saying f(n) < g(n) asymptotically and not exactly so for some constant values even

if f(n) > g(n) this doesn't matter as we are speaking asymptotically

Also when we say f(n) > g(n) asymptotically it means f(n) will grow faster than g(n) for all the values >= n0

see in the above we are taking values which are greater than or equal to n0 and not for every value of n

what i really don't understand is

f(n) + o(f(n)) = Θ(f(n))

here u said this equality is valid because we take o(f(n)) as anonymous function and not as set

but again u will write g(n) belongs to o(f(n)) which is contradicting to your above mentioned statement because u took o(f(n)) as a function and not as a set

What exactly is the convention that you are following

o(f(n)) in an equality or inequality is a

1. set
2. anonymous function

pls upvote if likes the explanation :)

by