big o recurrence relation

I have a simple recurrence relation describing algorithm complexity:
T(1) = 1
T(N) = 2 * T(N/2) + 1

What I attempted:
let k = log2(N)
T(N) = 2^K * T(N/(2^K)) + K
= 2^(log2(N)) * T(1) + k
= N + log2(N)

However I know that the complexity is 2N-1. Can someone point out where I am going wrong?
Edit:
I realized that
T(N) = 2^K * T(N/(2^K)) + K should be T(N) = 2^K * T(N/(2^K)) + N
which yields a final solution of 2N. I'm still losing the -1 constant and would like to know why.

Furthermore, if I have a relation
T(1) = 1
T(N) = 4 * T(N/2) + 1

Any suggestions how to approach this one?

Quote:

---

I realized that
T(N) = 2^K * T(N/(2^K)) + K should be T(N) = 2^K * T(N/(2^K)) + N

---

It should be T(N) = 2^K * T(N/(2^K)) + 2^(K-1) + 2^(K-2) + ... + 1 = 2^K * T(N/(2^K)) + 2^K - 1. When 2^K = N, this means T(N) = N * T(1) + N - 1 = 2N - 1.

Quote:

---

Furthermore, if I have a relation
T(1) = 1
T(N) = 4 * T(N/2) + 1

Any suggestions how to approach this one?

---

Approach it in the same way: expand the equation several times. I get T(N) = 4^K * T(N/(2^K)) + 4^(K-1) + 4^(K-2) + ... + 1 = (2^K)^2 * T(N/(2^K)) + ((2^K)^2 - 1) / 3.

If you need a big-O estimate, see the Master theorem.

Thank you very much! I missed the fact that the constant is multiplied by the number of recurring calls at each level.

Hi, I just had some time to work on the second recurrence with
T(N) = 4 * T(N/2) + 1

Everything works out except for the constant term. I describe it as the sum 4^0+4^1+..+4^N-1 and am not sure how to reduce it to a single function. The case 2^N was trivial. Is there any general solution to these?

I wrote it above: it's (4^N - 1) / 3. It's the sum of a geometric progression.