recurrence Master Theorm proof

Narek · #1 $Old$ October 29th, 2009, 03:27 PM

Hello guys,

well I attached 2 problems. I need to prove this using Master Theorm.
Can you help me please? I work on it and will post my efforts as soon as I get to some valid point.

Thank you

HallsofIvy · #2 $Old$ October 30th, 2009, 09:11 AM

Quote:

Originally Posted by Narek $View Post$

Hello guys,

well I attached 2 problems. I need to prove this using Master Theorm.
Can you help me please? I work on it and will post my efforts as soon as I get to some valid point.

Thank you

They give you a pretty good hint- set $T(n)= G(2^n)$ . What is T(n- c)? What do you get if you put those formulas for T(n) and T(n-c) into the recurrence equations?

Narek · #3 $Old$ October 30th, 2009, 01:43 PM

Hello guys!
I solved this one and I post the solution here

Thank you