CODEWITHSUNDEEP
big-ocomplexity-theoryasymptotic-complexity
djay
djay

Reputation: 375

How to find average/expected time for given expression?

(n * log_2 n) + (n^1.01 * (log_2 n)^10)

and is it better than O(n^1.03) ? If yes can one please explain, how to get an average case when worst case is known ?

Upvotes: 0

Views: 42

Answers (1)

Ken Wei
Ken Wei

Reputation: 3130

In theory, yes. O(n^p) is larger than O(n*log n) and O((log n)^k) for any p > 1 and k > 0.

For the first: n^p > (n * log n) <=> n^(p-1) > log n

For the second: n^p > (log n)^k <=> n^(p/k) > log n

Both of these inequalities hold for sufficiently large n.

Also notice that the base of the logarithm is irrelevant, because logs of different bases only differ by a constant factor, since log_b(x) = log_e(x)/log_e(b).

On the other hand, the only thing you can say about the average case, based on worst-case alone, is that it's no worse than the worst case.

A practical remark: for n^1.03 to become twice as large as n^1.01, you need (n^1.03)/(n^1.01) = 2 <=> n^0.02 = 2 <=> n = 2^50. That's huge!

Upvotes: 2

Related Questions