What is the time complexity for the worst case of this algorithm?

Question

I am analysing an algorithm that gives the location of a "peak value" of a square matrix (This means that the neighbors of the value are less or equal than the value). The algorith in question is very inefficient, because it goes checking values one by one, starting in the position (0,0) and moving to the neighbor that is more than the number. Here is the code:

def algorithm(problem, location = (0, 0), trace = None):
    # if it's empty, it's done!
    if problem.numRow <= 0 or problem.numCol <= 0:                                  #O(1)
        return None

    nextLocation = problem.getBetterNeighbor(location, trace)                       #O(1)
    #This evaluates the neighbor values and returns the highest value. If it doesn't have a better neighbor, it return itself

    if nextLocation == location:
        # If it doesnt have a better neighbor, then its a peak.
        if not trace is None: trace.foundPeak(location)                             #O(1)
        return location
    else:
        #there is a better neighbor, go to the neighbor and do a recursive call with that location
        return algorithm(problem, nextLocation, trace)                             #O(????)

I know that the best case is that the peak is in (0,0), and I determined that the worst case scenario is the following (Using a 10x10 matrix):

problem = [
 [0,   1,  2,  3,  4,  5,  6,  7,  8,  9],
 [0,   0,  0,  0,  0,  0,  0,  0,  0, 10],
 [34, 35, 36, 37, 38, 39, 40, 41,  0, 11],
 [33,  0,  0,  0,  0,  0,  0, 42,  0, 12],
 [32,  0, 54, 55, 56, 57,  0, 43,  0, 13],
 [31,  0, 53,  0,  0, 58,  0, 44,  0, 14],
 [30,  0, 52,  0,  0,  0,  0, 45,  0, 15],
 [29,  0, 51, 50, 49, 48, 47, 46,  0, 16],
 [28,  0,  0,  0,  0,  0,  0,  0,  0, 17],
 [27, 26, 25, 24, 23, 22, 21, 20, 19, 18]]

Note that it basically makes the algorithm go in a spiral and it has to evaluate 59 positions.

So, the question is: How do I get the time complexity for this case in particular and why is that? I know that all the operations are O(1), except for the recursion, and I'm lost

Answer 1

For an arbitrary matrix of size [m,n], as you showed with your example, we can break down the traversal of a given matrix made by this algorithm (A) as follows:

• A will traverse n-1 elements from the top-left corner to element 8,
• then m-1 elements from 9 to 17,
• then n-1 elements from 18 to 27,
• then m-3 elements from 27 to 33,
• then n-3 elements from 34 to 40,
• then m-5 elements from 41 to 45,
• then n-5 elements from 46 to 50,
• then m-7 elements from 51 to 53
• etc.

At this point, the pattern should be clear, and thus the following worst-case recurrence relation can be established:

    T(m,n) = T(m-2,n-2) + m-1 + n-1
    T(m,n) = T(m-4,n-4) + m-3 + n-3 + m-1 + n-1
    ...
    T(m,n) = T(m-2i,n-2i) + i*m + i*n -2*(i^2)

where i is the number of iterations, and this recurrence will continue only while m-2i and n-2i are both greater than 0.

WLOG we can assume m>=n and so this algorithm continues while m-2i>0 or while m>2i or for im/2 iterations. Thus plugging back in for i, we get:

    T(m,n) = T(m-m,n-m) + m/2*m + m/2*n -2*((m/2)^2)
    T(m,n) = 0 + m^2/2 + m*n/2 -2*((m^2/4))
    T(m,n) = 0 + m^2/2 + m*n/2 -2*((m^2/4))
    T(m,n) = m*n/2 = O(m*n)