0

What is the complexity of this function?

T(n) = T(n/3) + 1

Is the answer is O(n). But how the step?

Ok, so this is my answer:

T(n) = T(n/3) + 1

I use master theorem here,

So it got T(n) = aT(n/b) + f(n)

Compare the n^logb(a) with the f(n)

a = 1, b = 3

n^logb(a) = n^log3(1)
          = n^0
          = 1

f(n) = Θ(n^logb(a))

So the solution that I got is T(n) = Θ(logn)

This is my answer, but when I searched it, it said the answer T(n) = Θ(n) ?

AKSingh
  • 1,535
  • 1
  • 8
  • 17
MADFROST
  • 1,043
  • 2
  • 11
  • 29
  • 1
    Have you done any work on your own? *If you have, please mention it in your question.* – AKSingh Mar 27 '21 at 07:57
  • 1
    Why do you think the answer is O(n)? – derpirscher Mar 27 '21 at 08:16
  • @AKSingh I've updated my answer, is this correct ? – MADFROST Mar 27 '21 at 08:16
  • @derpirscher Because I'm not sure about my answer, I've updated my answer here, is there any wrong in my answer – MADFROST Mar 27 '21 at 08:18
  • 1
    I think `T(n) = Θ(logb (n))` is correct. – AKSingh Mar 27 '21 at 08:37
  • @AKSingh So, `b` here is not a Constant value? it must be included in the solution? I'm sorry for the lot question, Btw, thanks for your editing ! – MADFROST Mar 27 '21 at 08:52
  • 1
    @AKSingh I read the master theorem rules from [here](https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture3.pdf). From this i didn't see any `b` that include in the solution? – MADFROST Mar 27 '21 at 09:15
  • @Yes It is hardly mentioned in any articles. I did learn about it one famous book though. However, you need not worry. Since in algorithms `log n` implies *log n to the base 2* which is an *upper bound* for any `logb (n)`, that is, log n to the base b where be `b > 2`. – AKSingh Mar 27 '21 at 10:21

0 Answers0