I'm studying for an algorithms and data structures exam and came across this question in a past paper:
Note there is an error in the handout I think, the range of k should be from i to j not 1 to j, otherwise there is an infinite loop, which I guess is at least 2^n calls.
I've been going at it for a while and I have made some progress, but ultimately I have no clue where to go from here and there are no marking schemes available. I think I'll need to use the master theorem but can't figure out how to get it in the right shape. Any help would be appreciated even it it's just a link to a Wikipedia article that may be related.
I've tried formulating Ω(m[i,j]) as the sum of k = i+1 to j-1 (inclusive) of (2 + Ω(m[i,k]) + Ω(m[k, j])) which i think is correct, but after trying to simplify it I'm completely lost.