math - Solving the recurrence T(n) = T(n/2) + T(n/4) + T(n/8)? -

i'm trying solve recurrence t(n) = t(n/8) + t(n/2) + t(n/4).

i thought idea first try recurrence tree method, , use guess substitution method.

for tree, since no work being done @ non-leaves levels, thought ignore that, tried come upper bound on # of leaves since that's thing that's relevant here.

i considered height of tree taking longest path through t(n/2), yields height of log2(n). assume tree complete, levels filled (ie. have 3t(n/2)), , have 3^i nodes @ each level, , n^(log2(3)) leaves. t(n) o(n^log2(3)).

unfortunately think unreasonable upper bound, think i've made bit high... advice on how tackle this?

one trick can use here rewriting recurrence in terms of variable. let's suppose write n = 2^k. recurrence simplifies to

t(2^k) = t(2^k-3) + t(2^k-2) + t(2^k-1).

let's let s(k) = t(2^k). means can rewrite recurrence as

s(k) = s(k-3) + s(k-2) + s(k-1).

let's assume base cases s(0) = s(1) = s(2) = 1, simplicity. given this, can use variety of approaches solve recurrence. example, annihilator method (section 5 of link) great here solving recurrence, since it's linear recurrence. if use annihilator approach here, that

s(k) - s(k - 1) - s(k - 2) - s(k - 3) = 0

s(k+3) - s(k+2) - s(k+1) - s(k) = 0

(e³ - e² - e - 1)s(k) = 0

if find roots of equation e³ - e² - e - 1, can write solution recurrence linear combination of roots raised power of k. in case, turns out recurrence is similar tribonacci numbers, , if solve you'll find recurrence solves of form o(1.83929^k).

now, since know 2^k = n, know k = lg n. therefore, recurrence solves o(1.83929^{lg n}). let's let = 1.83929. solution has form o(a^{lg n}) = o(a^{(log_a n) / log_a2)}) = o(n^{1/log_a 2}). works out approximately o(n^0.87914...). initial upper bound of o(n^{lg 3}) = o(n^{1.584962501...}) weaker one.

hope helps!