ALGO(A,s,d)
m=d-s+1
if m>=2 then
q=⌊m/2⌋
return 2ALGO(A, s, s+q-1) + 3ALGO(A, s+q, d);
else
return 1
endif
I have this piece of code and I have to find the recurrence relation in function of n. The problem states that the algorithm is initially called with ALGO(A, 1, n). A is an array of size n, s and d are integer, q is the floor function of m/2.
The solution that I came up with is:
T(n) = 1 if n<2
T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + theta(1) if n>=2.
My reasoning was that if s=1 and d=n than m=n, q=⌊n/2⌋ and in the first recursive call i have s=1 and d=⌊n/2⌋ so m=⌊n/2⌋, for the second call s=s+q=1+⌊n/2⌋ d=n so m=⌈n/2⌉ so T(⌊n/2⌋) + T(⌈n/2⌉) + theta(1) because inside the if I calculate q which costs 1. I don't know if the solution that I came up with is correct or not and I don't know how to resolve it. For the resolution I don't know if I can say that T(⌊n/2⌋) + T(⌈n/2⌉) = T(n).
The recurrence relation you have given is correct, although the base case should also have θ(1): The value of 𝑇(1) is not the returned value (1), but the work (time complexity) needed to return it, which is θ(1):
𝑇(1) = θ(1)
𝑇(𝑛) = 𝑇(⌊𝑛/2⌋) + 𝑇(⌈𝑛/2⌉) + θ(1)
You cannot jump to the identity 𝑇(⌊𝑛/2⌋) + 𝑇(⌈𝑛/2⌉) = 𝑇(𝑛), because that is just the mirrored notation of the recursive case without the θ(1) term, but before you drop that θ(1) term you should probably show why you can do that.
One of the ways to approach this, is to observe that the recurrence tree is a full binary tree. For instance, for 𝑛=11 we can depict that binary tree as follows, only showing the values of the 𝑠 and 𝑑 parameters:
_______1,11________
/ \
___1,5__ __6,11__
/ \ / \
1,2 3,5 6,8 9,11
/ \ / \ / \ / \
1,1 2,2 3,3 4,5 6,6 7,8 9,9 10,11
/ \ / \ / \
4,4 5,5 7,7 8,8 10,10 11,11
The leaves of this tree represent the bases cases where return 1 is executed, while the internal nodes represent the cases where two recursive calls are executed.
Each edge represents one recursive call.
It is clear that the base case is executed for when 𝑠 equals 𝑑 and for every possible value of 𝑠 between 1 and 𝑛. So there are 𝑛 leaves. In any full binary tree the number of internal nodes is one less than the number of leaves, so that means the tree has 2𝑛−1 nodes, and 2𝑛−2 edges. Each node and each edge represents θ(1) complexity, so in total the algorithm has a time complexity of θ(𝑛).
In other words: because the number of internal nodes is of the same order as the number of leaves, you can leave out the θ(1) term from the recursive case.