#Back-substitution

Question

How to solve the following recurrence by back substitution.

T(n)= √2 *T(n/2) + c , for n>1

      =  a for n=1

Answer 1

T(n)= √2 *T(n/2) + c

=√2 [√2 *T(n/2 ²) +c] +c

= √2 ²  *T(n/2 ²) + √2c +c

=√2 ³ *T(n/2 ³) + √2 ²  c +√2c +c

...

=√2 ^k *T(n/2 ^k)+  √2 ^k-1  c+√2 ^k-2  c+...+√2c +c

put n/2 ^k  =1  => k=log ₂ n

=(√2) ^{log n} *T(1) + c [ 1 * (√2 ^{log n} -1)/(√2-1)]    (by applying g.p. series)

=n ^log ₂√2 *a + c [ (n ^log ₂√2 -1)/(√2-1)]

=a*n ^1/2  +c [ (n ^1/2 -1)/(√2-1)]  (Ignoring constants)

=O(n ^1/2).

Comments

O(n^1/2)