0
$\begingroup$

i have the following question:

Find lower and upper asymptotic bounds for the following recursive function:

$T(n)=n+T(\frac{n}2)+T(\frac{n}4)+...+T(\frac{n}{2^k})$

For the upper and lower bounds, can i say that:$$T(n)\le{n+kT(\frac{n}2)}$$ $$T(n)\ge{n+T(\frac{n}{2^k})}$$ And then continue by opening the function? If not, can anyone point me to the right direction?

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.