3

The recurrence relation of ternary search is T(n)= T(n/3) + 4, How 4 is in recurrence relation, since in ternary search it's log to the base 3 N, so only 3 partitions should be there ?

Ved sinha
  • 69
  • 3
  • 9
  • 2
    What's your source on this recurrence relation? That number 4 probably depends on some particular implementation being analyzed in a particular way. – templatetypedef Dec 25 '18 at 21:53
  • There was a question that either binary search or ternary search takes more number of comparisons, and in the solution this recurrence relation is given, so i was figuring out, how they could have gotten the 4. – Ved sinha Dec 26 '18 at 04:45
  • 2
    That recurrence relation is not correct for the algorithm normally referred to as 'ternary search'. You are probably thinking of something else. see: https://en.wikipedia.org/wiki/Ternary_search – Matt Timmermans Dec 26 '18 at 22:09
  • @Vedsinha Can you provide a direct link to that answer? That seems incorrect. – templatetypedef Dec 26 '18 at 22:35
  • That's a test series, so if i will give the link, it will require credentials @templatetypedef – Ved sinha Dec 27 '18 at 00:43
  • @MattTimmermans Yes, I got it, the recurrence is wrong. – Ved sinha Dec 27 '18 at 00:45

1 Answers1

2

Recurrence relation for ternary search is T(n) = T(n/3) + O(1) or even T(n) = T(2n/3) + O(1). The constant hidden in this O(1) depends on concrete implementation and how analysis was conducted. It could be 4 or 3, or some other value. Applying case 2 of Master theorem you still have O(log n).

Yola
  • 18,496
  • 11
  • 65
  • 106