Question

Derive a Θ-bound on the solution to the following recurrence. using iterative recursion and check your answer with master theorem result

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

Answer 1

Hi,

------------------------------------------------------------------

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

T(n) = T (n/3¹) + log n

=T(n/3²) + log(n/3¹)+log(n/3⁰)

=T(n/3³) + log(n/3²) + log(n/3¹)+log(n/3⁰)

  =T(n/3⁴) + log(n/3²) + log(n/3¹)+log(n/3⁰)

+................+

if n= 3^k then n/3^k =1 and k= log₃n and  T(1)=1

=T(n/3^k) +log(n/3^k-1) +  log(n/3^k-2) + ..............+ log(n/3²) + log(n/3¹)+log(n/3⁰)

=T(1) + log(n/3^k-1) +  log(n/3^k-2) + ..............+ log(n/3²) + log(n/3¹)+log(n/3⁰)

=1+ log(n/3^k-1) +  log(n/3^k-2)   + ..............+ log(n/3²) + log(n/3¹)+log(n/3⁰)

=1+ log(3^k/3^k-1) +  log(3^k/3^k-2)   + ..............+ log(3^k/3²) + log(3^k/3¹)+log(3^k/3⁰)   ∵ n= 3^k

=1+ log3 + log3² + .....+ log3^k-2 + log3^k-1 + log3^k

=1+ log₃3 + 2log₃3 + .....+ (k-2)log₃3 + (k-1)log₃3 + (k)log₃3  

=1+1+2+....+(k-2)+(k-1)+k

=1+ k(k+1)/2

=1+ k²/2 + k/2

=1+( log²n)/2 +( log​​​​​​​n)/2

now we ignore the constant terms and smaller terms.

T(n) = Θ(log²n) <---Answer

----------------------------------------------------------------------------------------------

Using Master Theorem

if T(n) =aT(n/b)+f(n) then T(n) = Θ(n^log_ba)

-----------------------------------------------------------

given T(n) = T (n/3) + log n

so a = 1 and b = 3 and f(n) =Θ log(n) where k =1

---------------------------------------------------

then T(n) = Θ(n^log_ba) = Θ(n^log₃1) = Θ(1)

here T(n) is logarithm time smaller than f(n)

----------------------------------------------------------

using master theorem special case :

if n^log_ba is logarithm time smaller than f(n) then T(n) = Θ(n^log_ba(log)^k+1)

------------------------------------------------------------------------

so T(n) = Θ(n^log₃1(log)¹⁺¹) ∵ log₃1 = 0

T(n) = Θ(n⁰(log)¹⁺¹) ∵ n⁰ = 1

T(n) = Θ(log_{​​​​​​​}²n) <---Answer

Conclusion: Iterative and master theorem both produce same result.

----------------------------------------------------------------------------------

Still if you have any doubt or need any kind of improvement, please let me know in comment section and if you like, Please upvote.

Thank You !