1

anybody can help to explain why this function

F(n) = F(n/3) + 1 with F(0) = 0

Can have time complexity of O(Log n) with log base 3.

Is there a mathematical notation or anything that can help explain to me how to get the result. Thanks

mtirtapradja
  • 129
  • 1
  • 9

1 Answers1

2

By substitution, it can be done simply:

F(n) = F(n/3) + 1 = F(n/3^2) + 1 + 1 = 1 + 1 + ... + 1 (log_3(n) times)

As each time n is divided by 3 and 1 is added to the result, if we suppose n = 3^k, F(n) = k. Hence, F(n) = O(log(n)). The constant (>1) in the base of the logarithm has not any impact on the order of complexity, i.e., log_a(n) = Theta(log_b(n)) (a,b > 1).

OmG
  • 18,337
  • 10
  • 57
  • 90