The Gateway to Computer Science Excellence

+3 votes

Please give an example case for which all the three conditions

$f(n)\neq O(g(n))$,

$f(n)\neq \Theta (g(n))$ and

$f(n)\neq \Omega (g(n))$

holds true.

$f(n)\neq O(g(n))$,

$f(n)\neq \Theta (g(n))$ and

$f(n)\neq \Omega (g(n))$

holds true.

+2

Please do not use '#' in GO -- it'll lead to duplicates as we do not use it anywhere. Meanwhile anyone who answers this correctly is strong in asymptotic notations.

+1

When there will be no equal , means either strictly grater than or strictly lesser than, in that cases all these three will be false.

Say $o\left ( g\left ( n \right ) \right )=${$f(n)$: there exists constant $c$ and $n_{0}$ such that $0< f(n)< cg\left ( n \right )$}

or

$\omega \left ( g\left ( n \right ) \right )=${$f(n)$: there exists constant $c$ and $n_{0}$ such that $0< cg\left ( n \right )<f(n)$}

Say $o\left ( g\left ( n \right ) \right )=${$f(n)$: there exists constant $c$ and $n_{0}$ such that $0< f(n)< cg\left ( n \right )$}

or

$\omega \left ( g\left ( n \right ) \right )=${$f(n)$: there exists constant $c$ and $n_{0}$ such that $0< cg\left ( n \right )<f(n)$}

0

@Satbir You meant "none of them holds" rt? It is better you can rewrite the sentence using $\neq$ instead of $=$ and none. And I suppose you know the answer here.

+1

See, first of all the condition that u have mentioned is not possible in case of any polynomial..so my thought process shifted to curve, and the first thing that came to my mind is sin and cosine curve..

Lets take some examples--> say we have sin 30 which is 0.5, now for the the same value of n, we have cos 30 = 0.87

so at this instance sin n = O( cos n)

but lets take another case.. sin 45 = cos 45 , so at this point sin n = theta (cos n)

now for sin 60 we have 0.86 but cos 60 =0.5

so here cos n= O(sin n)

and it will be more clear if u look at the sin and cosine graph,

so here we can say that-->

*f*(*n*)≠*O*(*g*(*n*)),

*f*(*n*)≠Θ(*g*(*n*)) and

*f*(*n*)≠Ω(*g*(*n*))

all holds true here as none of the condition is static.

0

@Hirak What about the remaining conditions for asymptotic notations? They are not merely <, > and =. What about the constants used in the definitions?

+1

Θ(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n >= n0}

going by the definition of theta for my function where i have taken f(n) = sin n and g(n)= cos n the condition of theta will never hold as for a certain value of n except n=(X*pi+45) [X= any whole number], sin and cos curve deviates from each other except these points .

O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0}

This definition also wont hold true even if we assign constant or even if we take whatever $n_0$ we want, same reason here also as sin n becomes negative for certain values and positive for certain in which cos tends to do the reverse..

Similar case for Omega..

That is why f(x) = sin x and g(x) =cos x works fine for this example. Even if we assign f(x)= cos x and g(x)= sin x it will not matter.

0

Nice. So, $\sin$ and $\cos$ becoming $0$ and negative are important here.

Is there some general behaviour for such functions which satisfy the asked conditions?

Is there some general behaviour for such functions which satisfy the asked conditions?

0

I think only oscillating curves intersecting at multiple points will exhibit such feature, other than sin and cos i am unable to think of other doing the same.

0

I thought of another possibilty, but i doubt its practicality

say we have function of O(n), say f(n)= O(n)

Now say we have another function g(n) = 1+2+3 +4+ 5+..upto n terms

so g(n) is O($n^2$).

so, f(n) =O(g(n)

But what about if n is infinity?

according to Ramanujan 1+2+3 +4+ 5+...... = -1/12

so g(n) = -1/12 , but f(n)= positive infinity

so this time , g(n) = O(f(n))

and it can be easily stated that they f(n) is not theta of g(n).

So this case also does satisfies-->

*f*(*n*)≠*O*(*g*(*n*)),

*f*(*n*)≠Θ(*g*(*n*)) and

*f*(*n*)≠Ω(*g*(*n*))

Doubt its practicality, but i think mathematicaly it is sound..

0

g(n) is showing upperbound as well as lowerbound for same function but not theta bound..

That is why it is satisfying the condition of the question

N must be non negative and here it is so..

That is why it is satisfying the condition of the question

N must be non negative and here it is so..

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,251 answers

198,044 comments

104,652 users