GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
126 views
  • T(n) = T(log n) + c
  • T(n) = T(log n) + log n
asked in Algorithms by Active (1.2k points)   | 126 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.



Top Users Jul 2017
  1. Bikram

    3960 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1848 Points

  4. joshi_nitish

    1654 Points

  5. Arjun

    1290 Points

  6. Hemant Parihar

    1184 Points

  7. Arnab Bhadra

    1100 Points

  8. Shubhanshu

    1052 Points

  9. Ahwan

    900 Points

  10. rahul sharma 5

    702 Points


24,018 questions
30,955 answers
70,327 comments
29,337 users