Proving a[n] = Θ(lg n): A Case Study

[e(ho0n3]

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?

 

[Hurkyl]

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.

 

[e(ho0n3]

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.

Sorry. What I meant was

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

My head is a total blank. I can't think of anything.