1

I've an assignment to explain the time complexity of a ternary tree, and I find that info on the subject on the internet is a bit contradictory, so I was hoping I could ask here to get a better understanding.

So, with each search in the tree, we move to the left or right child a logarithmic amount of times, log3(n), with n being the amount of String in the tree, correct? And no matter what, we would also have to traverse down the middle child L number of times, where L is the length of the prefix we are searching.

Does the running time then come out to O(log3(n)+L)? I see many people simply saying that it runs in logarithmic time, but does Linear time not grow faster, and hence dominate?

Hope I'm making sense, thanks for any answers on the subject!

Jskoven
  • 31
  • 1

1 Answers1

0

If the tree is balanced, then yes, any search that needs to visit only one child per iteration will run in logarithmic time.

Notice that O(log_3(n) = O(ln(n) / ln(3)) = O(ln(n) * c) = O(ln(n))

so the base of the logarithm does not matter. We say logarithmic time, O(log n).

Notice also that a balanced tree has a height of O(log(n)), where n is the number of nodes. So it looks like your L describes the height of the tree and is therefore also O(log n), so not linear w.r.t. n.

Does this answer your questions?

Berthur
  • 4,300
  • 2
  • 14
  • 28