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.


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.