0

By using master method the solution of this recurrence T(n) = 4T(n/2) + n2 is "n2*logbase2 N", but using recurrence tree; its tree height will be:

(No.of.Leaves)N=d^h ==> N=4^h ==> logbase4 N = h

and at-last T(n) = O(n^2*logbase4 N) will be its running time, but not "n^2*logbase2 N" as by master method. Am I right?

[Update # 1]

As I found, log base doesn't matter in case of Big O analysis. Thereby, O(n^2*logbase4 N) could be equal to O(n^2*logbase2 N) Asymptotically

Mehran
  • 306
  • 3
  • 15
  • 3
    The base of a log doesn't affect its asymptomatic growth. There are probably several questions to that effect on SO. – Teepeemm Jun 13 '14 at 12:36
  • But i think O(n^2*logbase4 N) is more reasonable than O(n^2*logbase2 N), actually i wrote ..base4.. in my Algorithm exam,as i assume it is more reasonable. – Mehran Jun 13 '14 at 12:43
  • 1
    It doesn't matter. You could have written logbase500. – Teepeemm Jun 13 '14 at 12:45
  • 1
    @Teepeemm I suggest [Is Big O(logn) log base e?](http://stackoverflow.com/questions/1569702/is-big-ologn-log-base-e) as a duplicate with useful answers. – Patricia Shanahan Jun 13 '14 at 13:13
  • 1
    The point is that big-O ignores constant factors, and the choice of logarithm base is a constant factor. – Patricia Shanahan Jun 13 '14 at 13:17
  • OK, constant factor doesn't matter, but O(n^2*logbase4 N) explains better than O(n^2*logbase2 N) as in binary-search case: O(logbase2 N ) explains better than O(logbase10 N). – Mehran Jun 13 '14 at 14:15

0 Answers0