I have the following function which computes the sum of all numbers from a to b. I'd like to know how to find its time complexity (without using the master theorem). I'd love getting an intuitive explanation and how to approach such problem.
def sum_func(a, b):
if a == b:
return a
mid = (a+b) // 2
return sum_func(a, mid) + sum_func(mid+1, b)
Say n is the size of the range, i.e. the amount of numbers to be added together. Imagine those numbers as the leaves of a binary tree, where each node in the tree represents a subrange, and when the function is called to sum that node's subrange, it makes two recursive calls represented by that node's two children in the binary tree.
A binary tree with n leaves has 2*n - 1 nodes, each representing a recursive call, so the recursive function is called O(n) times. Each time the function is called, it does O(1) work plus the recursive calls; therefore the total work done is O(n).