Is the height of this recursive tree $\lceil \log _{2} n \rceil$?

Question

I adapted the following code for a recursive binary cumulative sum function in Python:

import math
def fn(array, first, last):
    print(first, last, sep=', ')
    if first == last:
        return array[first]
    mid = math.floor((first + last) / 2)
    return fn(array, first, mid) + fn(array, mid + 1, last)

fn([0,1,2],0,2)

I then used this tool to visualize my recursive tree. Here's an example of the tree when $n$ (the size of the input array) is 7:

I made a mapping of several values of $n$ and the height of the tree, and noticed that the height corresponds to $\lceil \log _{2} n \rceil$, but I haven't seen this in any of my algorithmic analysis texts. Am I missing something or going against some convention?

Answer 1

Yes you cut a packet in two at each step and after k steps, you will obtain packets of size $n/2^{k}$.

You will be stopped when $n/2^{k+1}<1 \leq n/2^{k}$ i.e. $n<2^{k+1}$ and $2^k \leq n$

Considering $\log_2$, $k\leq \log_2(n)$ and $\log_2(n) <k+1$

Hence $\log_2(n)-1 < k \leq \log_2(n)$

This shows that your tree will have a depth k not exceeding $\lceil \log_2(n)\rceil$.