Let the following algorithm be:
sum(v, i, j) {
if i == j
return v[i]
else {
k = (i + j) / 2
return sum(v, i, k) + sum(v, k+1, j)
}
}
The time complexity of this algorithm is O(n), but how can I prove (in natural language) its complexity? The problem always gets divided in two new problems so that would be O(log n), but where does the rest of the complexity come from?
Applying master theorem yields the expected result, O(n).
Thanks.
From a high level perspective, your algorithm acts as if it is traversing a balanced binary tree, where each node covers a specific interval [i, j]. Their children divide the interval into 2, roughly equal parts, namely [i, (i+j)/2] and [(i+j)/2 + 1, j].
Let's assume that they are, in this case equal. (in other words, for the sake of the proof, the length of the array n is a power of 2)
Think of it in the following way. There are n leaves of this balanced binary tree your algorithm is traversing. Each are responsible from an interval of length 1. There are n/2 nodes of the tree that are the parents of these n leaves. Those n/2 nodes have n/4 parents. This goes all the way until you reach the root node of the tree, which covers the entire interval.
Think of how many nodes there are in this tree. n + (n/2) + (n/4) + (n/8) + ... + 2 + 1. Since we initially assumed that n = 2^k, we can formulate this sum as the sum of exponents, for which the summation formula is well known. It turns out that there are 2^(k+1) - 1 = 2 * (2^k) - 1 = 2n - 1 nodes in that tree. So, obviously traversing all nodes of that tree would take O(n) time.
Dividing the problem in two parts does not necessarly mean that complexity is log(n).
I guess you are referring to binary search algorithm but in that every division each half is skipped as we know search key would be in other side of division.
Just by looking at the sudo code , Recursive call is made for every division and it is not skipping anything. Why would it be log(n)?
O(n) is correct complexity.
The problem always gets divided in two new problems so that would be O(log n)-no. You are not discarding either half each time you divide. If you discard either half as in binary search then it is O(logn) otherwise you would compute all leaves of the recursion tree which is of the order of O(n).