# A[n] = Θ(lg n)?

1. Jul 20, 2004

### 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?

2. Jul 20, 2004

### Hurkyl

Staff Emeritus
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.

3. Jul 21, 2004

### e(ho0n3

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.