I was calculating the time complexity of the following recurrence relation given that T(1) = 1 :
T(n) = 2T(n/2) + Logn
I was calculating the value and this is where I reached:
T(n) = logn + 2log(n/2) + 4log(n/4) + 8log(n/8) + .....+ 1
I have tried solving this by opening log but I'm unable to reach O(n). I don't want any other method like substitution or root tree to be used. I want to use simple maths and reach O(n), please let me know if you have a clue about it.