tag:blogger.com,1999:blog-3722233.post110493150907730100..comments2024-08-02T19:37:12.269-05:00Comments on Computational Complexity: Big OmegaLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger25125tag: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-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>.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@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.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@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.comtag:blogger.com,1999:blog-3722233.post-1104940543676797502005-01-05T09:55:00.000-06:002005-01-05T09:55:00.000-06:00How is f(n) = O(g(n)) nice clear unambiguous?
If f...How is f(n) = O(g(n)) nice clear unambiguous?<br />If f(n) = O(g(n)) and h(n) = O(g(n)), do we have f(n) = h(n)?<br /><br />(No.)Anonymousnoreply@blogger.com