tag:blogger.com,1999:blog-3722233.post110493150907730100..comments2023-03-20T21:49:52.361-05:00Comments on Computational Complexity: Big OmegaLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger26125tag:blogger.com,1999:blog-3722233.post-8960413134356217562014-01-11T08:43:02.619-06:002014-01-11T08:43:02.619-06:00n0pe
sara khann0pe<br />sara khanAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46831132315027142162014-01-11T08:22:33.425-06:002014-01-11T08:22:33.425-06:00n0pen0peAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54884812916271662102012-07-01T08:54:01.681-05:002012-07-01T08:54:01.681-05:00Yes, Θ(n) which lie between O(n) and big-omega(n),...Yes, Θ(n) which lie between O(n) and big-omega(n),<br /><br />http://ip-techmania.blogspot.in/2012/06/analysing-big-oh-notation.htmlRavihttps://www.blogger.com/profile/01292091207506062163noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43719183492923834482012-04-07T23:58:29.753-05:002012-04-07T23:58:29.753-05:00in which case omega is required?in which case omega is required?Anonymoushttps://www.blogger.com/profile/08301840377228653900noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50543932413002365402011-05-21T21:42:22.166-05:002011-05-21T21:42:22.166-05:00nooooooooooooooooooooooooooooooooooooooooooooooooo...noooooooooooooooooooooooooooooooooooooooooooooooooooMuditha Gayan Dissanayakahttps://www.blogger.com/profile/16677086827904386000noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60303903618346691342008-09-29T03:18:00.000-05:002008-09-29T03:18:00.000-05:00Is there any positive function f(n) which is n...Is there any positive function f(n) which is neither O(n) nor big-omega(n)??Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76227237434336866702008-09-18T10:00:00.000-05:002008-09-18T10:00:00.000-05:00I have learn discrete math at Univ,so please show ...I have learn discrete math at Univ,<BR/>so please show me<BR/>how do I choose k for prove Big-O notation ?<BR/>what's principle?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87852969057891500962008-09-18T09:59:00.001-05:002008-09-18T09:59:00.001-05:00I have learn discrete math at Univ,so please show ...I have learn discrete math at Univ,<BR/>so please show me<BR/>how do I choose k for prove Big-O notation ?<BR/>what's principle?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65947727377373363492008-09-18T09:59:00.000-05:002008-09-18T09:59:00.000-05:00I have learn discrete math at Univ,so please show ...I have learn discrete math at Univ,<BR/>so please show me<BR/>how do I choose k for prove Big-O notation ?<BR/>what's principle?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73260575838042260712007-11-13T15:24:00.001-06:002007-11-13T15:24:00.001-06:00If f(x) from comment 1 abovewe know that f(x)*g(x)...If f(x)<=c1O(a(x)) and g(x)<=c2O(b(x))<BR/> from comment 1 above<BR/><BR/>we know that <BR/><BR/>f(x)*g(x) <= maxof(c1orc2) O(a(x)) * O(b(x))Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30658327597011793722007-11-13T15:24:00.000-06:002007-11-13T15:24:00.000-06:00If f(x) from comment 1 abovewe know that f(x)*g(x)...If f(x)<=c1O(a(x)) and g(x)<=c2O(b(x))<BR/> from comment 1 above<BR/><BR/>we know that <BR/><BR/>f(x)*g(x) <= maxof(c1orc2) O(a(x)) * O(b(x))Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58448592553802835962007-09-17T23:42:00.000-05:002007-09-17T23:42:00.000-05:00would logn! be big omega of nlogn?would logn! be big omega of nlogn?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1166360147990459862006-12-17T06:55:00.000-06:002006-12-17T06:55:00.000-06:00It is nature that Everybody get confusion with the...It is nature that Everybody get confusion with the representation f(n)=O(g(n)). One point I want to clearify is that the above mentioned representation is an assertion. Some author uses this represention(abuse of notation) keeping internally the meaning " f(n) is O(g(n)) or f(n) belongs to O(g(n))".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1105211314778815592005-01-08T13:08:00.000-06:002005-01-08T13:08:00.000-06:00> We should instead define f(n)=?(g(n)) by saying ...> We should instead define f(n)=?(g(n)) by saying for some <br />> constant c>0, f(n)? c g(n) for infinitely many n<br /><br />This seemed to have been on the cards for some time, atleast according to Knuth's paper, "Big Omicron and Big Omega and Big Theta". He refers to Hardy and Wright preferring "for infinitely many n" instead of "for large n". May be computer scientists did not find it necesary at that time!<br />amaramarhttps://www.blogger.com/profile/05058090398264083400noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1105061953597320232005-01-06T19:39:00.000-06:002005-01-06T19:39:00.000-06:00f(n) is O(g(n)) reads better than writing out set ...f(n) is O(g(n)) reads better than writing out set membership and is more accurate than using =.<br /><br />Given this notation there is not need to define the weak Ω at all: Why not simply say that f(n) is not o(g(n)) instead? <br /><br />The real temptation to use ∈ instead of 'is' comes when doing extensive arithmetic with O(g(n)) quantities.<br />It is awkward to keep connecting lines with 'which is'<br />instead of set equality.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1105042177390676572005-01-06T14:09:00.000-06:002005-01-06T14:09:00.000-06:00Use &isin; for ∈ and &Omega; for &Ome...Use &isin; for ∈ and &Omega; for Ω. You can see a list of special characters <A HREF="http://www.blogger.com/r?http%3A%2F%2Fwww.alanwood.net%2Fdemos%2Fent4_frame.html">here</A>.Lancehttps://www.blogger.com/profile/10719117059849994105noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1105041700997201482005-01-06T14:01:00.000-06:002005-01-06T14:01:00.000-06:00Hmm, when I posted the above, I thought I was typi...Hmm, when I posted the above, I thought I was typing a "belongs to" character (LaTeX $\in$), but it has appeared as "?" on this Firefox window on this Mac.<br /><br />-AmitCAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1105024100229454262005-01-06T09:08:00.000-06:002005-01-06T09:08:00.000-06:00Count one more vote for the "?" crowd. :-) Of cour...Count one more vote for the "?" crowd. :-) Of course, in keeping with tradition I do use "= O(g(n))" in writing, but I wish everyone would move to the more technically correct "?". The first anonymous commenter has already pointed out my main problem with "=".<br /><br />-- Amit ChakrabartiAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1104988568705717222005-01-05T23:16:00.000-06:002005-01-05T23:16:00.000-06:00Thanks, makes perfect sense now. -JonThanks, makes perfect sense now. -JonAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1104988398963670552005-01-05T23:13:00.000-06:002005-01-05T23:13:00.000-06:00I got that backwards. Should have been "f(n) ...I got that backwards. Should have been "f(n) is Ω(g(n)) iff f(n) is not o(g(n))". I'll fix it in the post.Lancehttps://www.blogger.com/profile/10719117059849994105noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1104987762904438452005-01-05T23:02:00.000-06:002005-01-05T23:02:00.000-06:00I'll try again. (Whatever happened to Unicode?)
I...I'll try again. (Whatever happened to Unicode?)<br /><br />I don't understand the statement: "f(n)=Omega(g(n)) iff g(n) is not o(f(n))"<br /><br />Consider the case where g(n) represents constant time, and f(n) is say exponential time. Clearly g(n) is a lower bound for f(n), so the condition f(n)=Omega(g(n)) holds. Also clearly, f(n) is a loose upper bounds for g(n), so g(n) is o(f(n)), contradicting the statement above.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1104986889558097602005-01-05T22:48:00.000-06:002005-01-05T22:48:00.000-06:00I don't understand the statement: "f(n)=?(g(n)) if...I don't understand the statement: "f(n)=?(g(n)) iff g(n) is not o(f(n))"<br /><br />Consider the case where g(n) represents constant time, and f(n) is say exponential time. Clearly g(n) is a lower bound for f(n), so the condition f(n)=?(g(n)) holds. Also clearly, f(n) is a loose upper bounds for g(n), so g(n) is o(f(n)), contradicting the statement above.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1104967033046311802005-01-05T17:17:00.000-06:002005-01-05T17:17:00.000-06:00Usually "f(n)=o(g(n))" means that f(n)/g(n)-->0...Usually "f(n)=o(g(n))" means that f(n)/g(n)-->0, or alternatively that for every c>0, |f(n)|<c|g(n)| for n large enough.<br /><br /> - Eldar.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1104951176378245022005-01-05T12:52:00.000-06:002005-01-05T12:52:00.000-06:00I like the set definition myself, but in writing I...I like the set definition myself, but in writing I might say "T(n) is O(n)" where the "is" is substituting a "=". (Equality is two directional, while "is" is one directional, depending on what the definition of "is" is.)<br /><br />I'm confused by the litte-oh defintion: isn't f(n)<c*g(n) what it means? (I.e., the same as the big-O defintion, but with a < instead of a >=, and c is always positive?)Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1104949470540914022005-01-05T12:24:00.000-06:002005-01-05T12:24:00.000-06:00I use the "f(n)=O(g(n))" notation myself, but I mu...I use the "f(n)=O(g(n))" notation myself, but I must admit that the "f(n) \in O(g(n))" option has merit. First, it is useful to think of this as a set of functions when doing "O arithmetic", as in "(1+o(1))g(n)" or "n^{(O(1))}". Also, it would help the lower bound issues by writing "f(n) \not\in O(g(n))", and saving the Omega notation for the few cases where we need it as it is now.<br /><br />On the other hand most of us are already used to "f(n)=O(g(n))", and it is not as if as we are anywhere near the level of notational abuse of, say, Quantum Field Theory...<br /><br /> - Eldar.Anonymousnoreply@blogger.com