Yea your right, it is a O(N) solution. I remembered much later that such recursions complexity can be solved by the Master method. You can check the video explaining it here https://www.youtube.com/watch?v=pXED5yrNyMg. The solution is pretty much simple substitution into the formula after that.