Read about asymptotic bounds | 2 Discussions | Page 1

  1. 22990atinesh

    Solving recurrence by changing variables

    Consider the below recurrence ##T(n) = 2 T(\sqrt(n)) + \log n## substituting ##\log n = m \implies n = 2^m## ##T(2^m) = 2 T(2^{\frac{m}{2}}) + m## substituting ##S(k) = T(2^m)## I'm getting below equation ##S(k) = 2 S(\frac{k}{2}) + m## How can I change 'm' to 'k' in above equation.
  2. A

    Asymptotic bound of n lgn

    When considering the asymptotic bounds for n lgn, for what value of a in na does n lgn satisfy O(na) and for what value does it satisfy Ω(na)? For example n lgn = O(n1.261) but n lgn = Ω(n0.797). Can someone please tell me where for what a does Ω change to O? Also how does the answer change...
Top