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

+1 vote
1 answer
1
asked in Algorithms by kallu singh Junior (657 points)   | 35 views
+1 vote
0 answers
3


Top Users Sep 2017
  1. Habibkhan

    8312 Points

  2. Warrior

    2862 Points

  3. rishu_darkshadow

    2796 Points

  4. Arjun

    2766 Points

  5. A_i_$_h

    2526 Points

  6. manu00x

    2094 Points

  7. nikunj

    1980 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1810 Points

  10. SiddharthMahapatra

    1718 Points


26,283 questions
33,842 answers
80,383 comments
31,193 users