3 votes 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. Algorithms asymptotic-notation self-doubt algorithms + – Satbir asked Jun 1, 2019 • retagged Jun 22, 2019 by Cristine Satbir 1.4k views answer comment Share Follow See all 30 Comments See all 30 30 Comments reply Arjun commented Jun 1, 2019 reply Follow Share 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. 2 votes 2 votes srestha commented Jun 1, 2019 reply Follow Share 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)$} 1 votes 1 votes Satbir commented Jun 1, 2019 reply Follow Share Can you give an example @srestha 0 votes 0 votes srestha commented Jun 1, 2019 reply Follow Share @Satbir Suppose $2n+10=O(n)$ but $\\=o(n^{2})\\ \text{or}\\ o(n^{3})$ 0 votes 0 votes Arjun commented Jun 1, 2019 reply Follow Share @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 votes 0 votes Satbir commented Jun 1, 2019 reply Follow Share @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 ? 0 votes 0 votes Hirak commented Jun 1, 2019 reply Follow Share @Satbir f(n) = sin n g(n) = cos n 2 votes 2 votes Satbir commented Jun 1, 2019 reply Follow Share @Hirak can you explain in detail. 0 votes 0 votes Hirak commented Jun 1, 2019 reply Follow Share 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. 1 votes 1 votes Arjun commented Jun 1, 2019 reply Follow Share @Hirak What about the remaining conditions for asymptotic notations? They are not merely <, > and =. What about the constants used in the definitions? 0 votes 0 votes Hirak commented Jun 1, 2019 reply Follow Share @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. 1 votes 1 votes Arjun commented Jun 1, 2019 reply Follow Share 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 votes 0 votes Hirak commented Jun 1, 2019 reply Follow Share @Arjun sir general behaviour means? 0 votes 0 votes Arjun commented Jun 1, 2019 reply Follow Share For certain type of functions the given condition always holds -- for which type of functions? 0 votes 0 votes Hirak commented Jun 1, 2019 reply Follow Share 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 votes 0 votes Arjun commented Jun 1, 2019 reply Follow Share Is oscillation mandatory? Is intersection mandatory? 0 votes 0 votes Hirak commented Jun 1, 2019 reply Follow Share @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 votes 0 votes srestha commented Jun 1, 2019 reply Follow Share summation strictly increasing func., has asymptotically upper bound isnot it?? 0 votes 0 votes Hirak commented Jun 1, 2019 reply Follow Share @srestha https://medium.com/@marktdodds/the-ramanujan-summation-1-2-3-1-12-a8cc23dea793 0 votes 0 votes srestha commented Jun 1, 2019 reply Follow Share Actually , that is $O\left ( 1 \right )$, right?? oscillation is more appropriate 0 votes 0 votes Hirak commented Jun 1, 2019 reply Follow Share as it is O(1) hence g(n)=O(f(n)) here.. Mathematically it is correct.. 0 votes 0 votes srestha commented Jun 1, 2019 reply Follow Share how?? '=' is not a violation of condition and isnot it satisfying $\Omega (n)$ 0 votes 0 votes srestha commented Jun 1, 2019 reply Follow Share Moreover, to find tight bound, when n is sufficiently large, f(n) should be non negative 0 votes 0 votes Hirak commented Jun 1, 2019 reply Follow Share 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 votes 0 votes srestha commented Jun 1, 2019 reply Follow Share What is upper bound, lower bound and tight bound for an A.P.?? 0 votes 0 votes srestha commented Jun 1, 2019 reply Follow Share This question is nothing but, it is satisfying irreflexive property of the relation 0 votes 0 votes srestha commented Jun 2, 2019 reply Follow Share @Hirak chk it once:https://stackoverflow.com/questions/56412070/example-of-irreflexive-relation-in-asymptotic-notation/56412572?noredirect=1#comment99423526_56412572 0 votes 0 votes Hirak commented Jun 2, 2019 reply Follow Share 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. 0 votes 0 votes Satbir commented Jun 2, 2019 reply Follow Share @Hirak It would be much better if write your answer and discuss there in comments. 1 votes 1 votes commenter commenter commented Sep 27, 2019 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 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 Aprajita sachdev answered Jun 3, 2019 Aprajita sachdev comment Share Follow See all 0 reply Please log in or register to add a comment.