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


    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook