Python : complexity of counting occurrences in columns-CodePudding

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²)?

CodePudding user response：

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.

CodePudding user response：

Prob. you can try different approach instead of two loops?

AA = sum(A, [])     # O(n)    flatten the matrix 

total = sum(1 for x in AA if x == 'X')    #  another O(n) 

# so this could be considered O(n) ---- drop the constant 2 here (2 O(n))