I believe we have to use a variant of master theorem...can someone suggest me how to find complexity of such equation which doesn't directly fit into Masters theorem.

  • Good example here, if you actually want to use Master Theorem: stackoverflow.com/a/6094889 – Robert Harvey Mar 16 '16 at 22:40
  • 2
    Otherwise... What is Big O and how do I calculate it? – Robert Harvey Mar 16 '16 at 22:41
  • @RobertHarvey : I am unable to figure out the complexity for this..I felt the n^2.93(logn)^93 grows faster than n^3 but the answer is other way its O(n^3) is what i think – kranthi kumar Mar 16 '16 at 23:01
  • Graph each one, using different values of n. – Robert Harvey Mar 16 '16 at 23:02
  • 1
    Please edit your question to include a proper mathematical notation of the function. It is not clear how your exponents are parenthesized. – 5gon12eder Mar 17 '16 at 11:08

I'd first put parentheses around the expressions to make clear what the right side actually is. Once it is clear that it is (n ^ 2.93) * ((log n)^93) = o (n^3) the solution is easy, but rather pointless: If log n is the natural logarithm, then for n ≥ 8 or so no computer in the world will ever solve the problem. If log n is base 10 logarithm, then the same is true for n = 100.

If you graph it and conclude that (n ^ 2.93) * ((log n)^93) is always greater than n^3: If log is the natural logarithm, then n^3 is larger when x is around 10^5445.

PS. codesInChaos is apparently not very well versed with the use of little-o. It is very common to use = and not "element of" with big-O / little-o notation, and anything that grows slower than n^3 is indeed o (n^3).

  • Shouldn't your = be a ? – CodesInChaos Mar 17 '16 at 10:58
  • It's common to use = with big O / little o. – gnasher729 Mar 17 '16 at 11:30
  • 1
    Sounds like a horrible idea. Especially in this case, since o(n^2.93 * (log n)^93) ⊂ o(n^3) and thus o(n^2.93 * (log n)^93) ≠ o(n^3). – CodesInChaos Mar 17 '16 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.