Python function time complexity

Question

I am wondering if I calculate the time complexity correctly with the function below.

mat is a list of lists.

k is an integer.

def kWeakestRows(mat, k): 
    hashmap = {}
    for i in range(len(mat)):
        hashmap[i] = Counter(mat[i]).get(1)
        if hashmap[i] == None:
            hashmap[i] = 0
            result = []
    while len(result) < k:
        key = min(hashmap, key=hashmap.get)
        result.append(key)
        hashmap.pop(key)
    return result

My thought is since it iterates through one for loop (for size of a list) and one while loop (for the value of k), it is O(N). But in the for loop, I use Counter to count the 1s in the inner list, it would be O(N*M).

In addition, my guess on space complexity is also O(N) as it fills the hashmap with the elements in the given list (mat), and it fills a list (result) by the value of k.

Please let me know if I am wrong.

Answer 1

Yes! What you have assumed is correct in terms of both time and space complexity , the for loop at first iterating till end of the "mat" and it is obviously O(N) and while loop goes in accordance of length "result"- list, since there won't exist any kind of nested loops it doesn't go beyond O(N). And to take counter function into account the time complexity would increase in terms of the no. of checks, so it is of O(N*M). Also with space complexity the only memory part that we using is hashmap dict which get appended with 0 in for loop and minimum value of mat itself ,so it is also of O(N) at worst case itself.