Question

Change of variables process help

I'm trying to learn how to properly use the change of variables technique (also known as domain transformations)

My textbook has the following as an example

T(n) = T(n/2) + 1
T(1) = 1
n = 2^k -> k = lgn

sub 2^k for n to get
T(2^k) = T(2^(k-1)) + 1

then set tk = T(2^k) in that recurrence to get

tk = tk-1 + 1 --> (k-1 is subscripted)

That form is part of a theorem to get a general solution of

tk = c1 + c2

Now substitute T(2^k) into this general solution to get

T(2^k) = c1 + c2k

then sub n for 2^k

1. Substitute T(2^k) for

Answer 1

Updating with rest of question:

1. Sub T(2^k) for tk in the general solution to get

T(2^k) = c1 + c2k

2. sub n for 2^k and lgn for k to get

T(n) = c1 + c2lgn

we know T(1) = 1

so we can compute the constants to obtain T(n) = 1 + lgn

Answer 2

so the whole process is rather confusing to me. Can anyone walk through the solution if instead

T(n) = T(sqrt(n)) + 1 rather than above where t(n) = (n/2) + 1

Answer 3

I figured out that I can sub 2^k for n and get

T(2^k) = T(2^(k/2) + 1

Now I have to make a recurrence out of this?

Answer 4

You could do the thing thing they have done in the example
\[\text{ Let } t_k=T(2^k) \\ \text{ so } t_{\frac{k}{2}}=T(2^{\frac{k}{2}}) \\ \text{ and so you have the recurrence relation } \\ t_k=t_\frac{k}{2}+1 \\ \]

Answer 5

that's weird
that looks like your first recurrence relation :p

Answer 6

you know except you have T's instead of t's

Answer 7

It looks like the recurrence relation has to comply with the theorem:

a0tn + a1tn-1 .... = (b^n)(p(n))

So there must be some way to alter the equation to make tk/2 -> tk-1

Answer 8

I think I've made more sense of this.

T(n) = c1 +c2(lgn) can stay the same for this case

We found that tk = tk/2 + 1

So knowing that t(2) = 1 we can use that to solve for t(4) (since the question says n = 2^k)

t(4) = tk/2 + 1
t(4) = t2 + 1
t(4) = 1 + 1
t(4) = 2

so now we have t(0) = 0, t(2) = 1, t(4) = 2 we can solve for the constants c1 and c2

So

0 = c1 + c2
1 = c1 + c2
2 = c1 + 2(c2)

to solve for c1 and c2 with 3 equations we use gaussian elimination correct?

I'm rusty on guassian elimination so if anyone has a good link to learn the method quick that would be great!