1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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