The Gateway to Computer Science Excellence
+3 votes
186 views
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.
in Algorithms by Boss (21.5k points)
retagged by | 186 views
+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)$}
0

Can you give an example @srestha

0

@Satbir

Suppose $2n+10=O(n)$ but $\\=o(n^{2})\\ \text{or}\\ o(n^{3})$

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. 

0

@Arjun Sir ,updated the question. Yes you are correct.

@srestha

so you are saying that f(n) = 2n+10 and g(n) = $n^2$ right ?

+2

@Satbir

f(n) = sin n

g(n) = cos n

0

@Hirak

can you explain in detail.

+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

@Arjun sir

Θ(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?
0

@Arjun sir

general behaviour means?

0
For certain type of functions the given condition always holds -- for which type of functions?
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
Is oscillation mandatory? Is intersection mandatory?
0

@Arjun Sir

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
summation strictly increasing func., has asymptotically upper bound

isnot it??
0
Actually , that is $O\left ( 1 \right )$, right??

oscillation is more appropriate
0
as it is O(1) hence g(n)=O(f(n)) here..

Mathematically it is correct..
0
how??

'=' is not a violation of condition

and isnot it satisfying $\Omega (n)$
0
Moreover, to find tight bound, when n is sufficiently large, f(n) should be non negative
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..
0
What is upper bound, lower bound and tight bound for an A.P.??
0

This question is nothing but, it is satisfying irreflexive property of the relation

0
I think what he is trying to say is that time taken to calculate them will be O(1) for both f(n) and g(n), and i cant deny with him as well.

But strictly going by definition and (even from the graphs) of asymptotic notation we can see that at certain point sin x upperbounds cosx and vice versa.
+1

@Hirak

It would be much better if write your answer and discuss there in comments.

0
How does sin and cos functions satisfy those 3 conditions? If I take a constant then one function will be completely above the other function so it doesn't satisfy the conditions.

1 Answer

0 votes
n^(1+sin n) and n^(1+cos n) these two functions are incomparable so satisfy all three properties given . Correct me if wrong
by (93 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,422 answers
195,195 comments
99,834 users