algorithm help

[Balain]

So for my algorithms course I need to find a good guess for a tight asymptotic bound for T(n) = T(n/2) + T(n/4) + T(n/8) + n (where all the fractions are floors). We need to use the iteration method, but I am just not seeing it. So far I have...
T(0) = 0
T(1) = 1
T(2) = T(1) + T(0) +T(0) + 2 = 1 + 2 = 3
T(3) = T(1) + T(0) +T(0) + 3 = 1 + 3 = 4
T(4) = T(2) + T(1) +T(0) + 4 = 4 + 4 = 8
T(5) = T(2) + T(1) +T(0) + 5 = 4 + 5 = 9
...
T(8) = T(4) +T(2) +T(1) + 8 = 12 + 8 = 20
T(9) = T(4) +T(2) +T(1) + 9 = 12 + 9 = 21
...
T(16) = T(8) + T(4) + T(2) + 16 = 31 + 16 = 47
T(17) = T(8) + T(4) + T(2) + 17 = 31 + 17 = 48

Using powers of two and reducing I get:

T(0) = 0
T(2^1) = 2 + 1
T(2^2) = 4 + 2 + 1 + 1
T(2^3) = 8 + 4 + 2 +1 + 2 +1 + 1

Grouping them getting:
T(2^1) = (2) + (1)
T(2^2) = (4+2) + (1) +(1)
T(2^3) = (8+4+2+1) + (2+1) + (1) or

I have been trying various summations and products but just not seeing it. Any advice would be greatly appreciated.

[Selpharia]

My initial guess is O(nlogn), simply because you're doing something that caps out at O(n) (because of the +n term) log n times (because after you reach the log(n)th iteration, everything else is constant time. Also , the terms of T(n) after T(n/2) (except the n) are asymptotic to n/2, which suggests to me that this looks suspiciously like Tn)=2T(n/2) + f(n) where c = 1 = log base 2 of 2 so the proper answer according to Master Theorem is O(nlogn). But I'm jut an amateur, so I could be totally wrong. I'd try a tree diagram to confirm this, and you might be able to get a tighter bound with real knowledge.

[Douglas]

Speaking from no research, "use the iteration method" to me suggests that you're supposed to come up with a base bound that works for low values, then plug it in on the right side of the equation and see what that produces for the left side, then take that as your new bound and repeat the process until you get back out what you put in.

I don't know if this will actually end up settling on something, but it's worth a try.

[Balain]

Thank you very much I think that helps

[Eloel]

T(n/2) = T(n/4) + T(n/8) + something positive

=>

T(n) < 2T(n/2) + n

=>
T(n) = O(nlogn)

Let's guess it's also a lower bound.

T(n) > c*(n/2)logn + c*(n/4)logn + c*(n/8)logn + (1-c/2-c/4-c/8)n

= (c/2 + c/4 + c/8)logn + (1-c/2-c/4-c/8)n

Pick c = 8/7
Then, T(n) > nlogn
=>
T(n) = omega(nlogn)
=>
T(n) = theta(nlogn)

I have no idea how to find this via iterations though.

[Tarqiup Inua]

I'd try Akra-Bazzi method - not that I have any experience in using it whatsoever.

It does seem to be something devised exactly for solving problems of this nature.

http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method

[Jay R]

So for my algorithms course I need to find a good guess for a tight asymptotic bound for T(n) = T(n/2) + T(n/4) + T(n/8) + n (where all the fractions are floors).

Look at just the power of 2s, since they are the easiest to calculate.

Let U(n) = T(2^n)

Then U(n) = U(n-1) + U(n-2) + U(n-3) + n
This makes a sequence that is strictly recursive on the last three values, and thus, absurdly easy to calculate in Excel.

U(0) = T(1) = 1
U(1) = T(2) = 3
U(2) = T(4) = 8
U(3) = T(8) = 20
etc.

I've run it out to U(200) = T(1.60694E+60), and it's clear that T(n)/n is always less than 8.

So the sequence is O(8n), and 8n is a hard upper limit.

Proof by induction:
For the first three, u(i) < 8 * 2^i, by inspection.
[u(0) = 1 < 8; u(1) = 1 < 16; and u(2) = 8 < 32]

Assume any three U(i) < 8*2^i for all values up to i.

So U(i) < 8*2^i = 2^(i+3)
U(i-1) < 8*2^(i-1) = 2^(i+2)
U(i-2) < 8*2^(i-2) = 2^(i+1)

Then U(i+1) = U(i) + U(i-1) + U(i-2) + 2^(i+1)
< 2^(i+3) + 2^(i+2) + 2^(i+1) + 2^(i+1)
add the last two terms
= 2^(i+3) + 2^(i+2) + 2^(i+2)
add the last two terms
= 2^(i+3) + 2^(i+3)
add the last two terms
= 2^(i+4)

So u(i+1) < 2^(i+4) = 8 * 2^(i+1)

Therfore by induction, it will always be true.