CAN ANYONE HELP ME SOLVE THIS PROBLEM...I KNOW I SHOULD USE SUBSTITUTION BUT
THE NEXT STEP IS BLUR! PLEASE!
Use Master Theorem to prove that
a) The *Chip and be Conquered *recurrence *T(n)=bT(n-c)+f(n), n
>smallSize, b>1, c>0* has solution *T(n)**Î**Q**(bn/c)*, if *f(n) **Î** **
O**(nA), *for some *A>0*.
b) The *Chip and Conquer* recurrence *T(n)=T(n-c)+f(n)*, *n**
>smallSize*, *c>0* has solution *T(n) **Î** **Q**(nA+1),* if *f(n) **Î** *
*Q**(nA)*, for some *A**³**0*.
*Hint*: Use the substitution *T(n)=G(2n) *and change of variable *2n=m*.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
