The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
154 views
  • T(n) = T(log n) + c
  • T(n) = T(log n) + log n
asked in Algorithms by Active (1.3k points) | 154 views

For 

  • T(n) = T(log n) + c 
       T(n)=log*n
Can  u plz  show how ?

yes......
see how our problem of size n is reducing...like
  n -> logn ->loglogn -> loglogn ..................-> 1
it must b need 2 give there that T(1) is constant 
now see defn of log*n "In computer science, the iterated logarithm of n, written log* n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1. "
  so there r log*n such iterations nd cost of each is c hence it is clog*n

Please log in or register to answer this question.

Related questions

0 votes
0 answers
2
+1 vote
1 answer
3
asked in Algorithms by kallu singh Junior (765 points) | 51 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,066 questions
36,872 answers
91,629 comments
34,760 users