How to find the time comlexity when comparing sublists?

Question

def check_lists(list_1, list_2):
    if list_1 == None or list_2 == None:
        return None
    for i in range(len(list_1)):
        if list_1[i] != list_2[i]:
            return None
    return list_1

def check_sublists(lst, fir, la):
    mid = (la + fir) // 2
    if (la - fir == 0):
        return lst[fir]  
    if (la - fir == 1):
        return check_lists(lst[fir], lst[la])
    return check_lists(check_sublists(lst, fir, mid), check_sublists(lst, mid + 1, la))

lst = [[1, 2, 3], [1, 2, 3], [1, 2, 6], [1, 2, 3]]

result = check_sublists(lst, 0, len(lst) - 1)
print(result)

So the function check_lists compares two lists using a for loop so it is O(k), in this case it will be used to compare the sublists with each other. The point is to check if all sublists are the same. The function check_sublists is the function that actually compares its sublists recursively. By using master theorem I get a=b=2. Also the largest sublist size is given by k. And nested list size is n. I am supposed to describe time complexity with these 2 variables. But using master theorem I am stuck because f(n) depends on k. I mean the non recursive part is k + constants. How am I supposed to do this?

Answer 1

The worst case materialises when all elements of the top-level list are equal, as then the None condition in the check_lists is never true.

The base case of recursion hits when the sublist only has 1 or 2 elements. In the latter case check_lists compares two adjacent elements of the top-level list.

The recursive case also calls check_lists, with one element taken from the left partition, and one element taken from the right partition. It doesn't really matter which element from those partitions gets selected/returned: when we get an element back, it means they were all the same in that partition anyway, so we can imagine that it would have been the rightmost element from the left partition and the leftmost element from the right partition.

If we account for the elements in that way, we can see that all adjacent elements of the top-level list are subject to a call of check_lists, and exactly once. In a list of 𝑛 elements there are 𝑛−1 adjacent pairs, so we can conclude that exactly 𝑛−1 calls of check_lists are made. As each call has a worst case time complexity of O(𝑘), the overall time complexity is O(𝑛𝑘).