>>13559136This is a stuffy way of showing something. Better way is this:
The algorithm described by this time recurrence does constant work per step (the + 1) and then cuts the input size by a half. Then that does a constant amount of work and cuts by a half, and so on. How many times can you cut n by half? Well, that’s the amount of times 2 divides n…which is example log n (here log is assumed base 2). Now, you cut log n times, and each time you’re doing constant work, so your work is constant added to itself log n times, which is O(log n).
