Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A[n] = Θ(lg n)?

  1. Jul 20, 2004 #1
    a[n] = Θ(lg n)!?

    Suppose {a[n]} is an increasing sequence and whenever m divides n, then

    a[n] = a[n/m] + d

    where m is a positive integer and d is a real number. Show that a[n] = Θ(lg n).

    a[n/m] + d ≤ a[n/2] + d, and with this I can show that a[n] = O(lg n). All I need to do is show that a[n] = Ω(lg n). This is where I'm stuck. Any hints?
     
  2. jcsd
  3. Jul 20, 2004 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    To show that something is in omega(log x), it suffices to find some sequence {x_i} such that a[x_i] grows like log x.

    By the way, I'm disconcerted with your reasoning that it is in O(log x); what if n is odd? I suppose you're just abbreviating the complete proof you have.
     
  4. Jul 21, 2004 #3
    Sorry. What I meant was

    [tex]a_n = a_{\lfloor n/2 \rfloor} + d[/tex]

    My head is a total blank. I can't think of anything.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A[n] = Θ(lg n)?
  1. N /n! = ? (Replies: 21)

  2. Sl(n), su(n) (Replies: 2)

Loading...