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.
Asked
Active
Viewed 682 times
-3
-
Good example here, if you actually want to use Master Theorem: http://stackoverflow.com/a/6094889 – Robert Harvey Mar 16 '16 at 22:40
-
2Otherwise... [What is Big O and how do I calculate it?](http://programmers.stackexchange.com/questions/132331/what-is-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
-
if we graph each one....always n^2.93(logn)^93 seems greater all time – kranthi kumar Mar 16 '16 at 23:03
-
@kranthikumar: If you graph it, on a paper that stretches from one end to the universe to the other, yes. You'd have to go beyond that. – gnasher729 Mar 17 '16 at 08:51
-
1Please [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
1 Answers
-1
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).
gnasher729
- 42,090
- 4
- 59
- 119
-
-
-
1Sounds 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