Python : complexity of counting occurrences in columns

feCamp 0
Viewed 22
A = [['X', 'X', 'O'],
     ['X', 'X', 'X'],
     ['O', 'X', 'X']]

def count_X():
    for i in range(3):
        total = 0
        for j in range(3):
            if A[i][j] == 'X':
                total += 1
        print(total)

Is there any simpler solution without nested for loops O(n²)?

2d time-complexity matrix count list
1 Answers

No, there isn't. First of all, you need to loop the rows, because you need the occurrence for each rows, that's already ON(n). Now, for each row, you have n elements and you do not know in advance which is 'X' and which isn't, so you loop all items, which is again O(n). Since you have an algorithm of O(n) that executes another algorithm of O(n) complexity, the actual complexity is O(n²). You cannot reliably get the total for each row's each element without looping the rows and their elements.

Lajos Arpad0
Related