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?