0

I wrote an algorithm in Python that can multiply matrices of positive integers, but I don't know how to measure its time complexity. The Python code for the algorithm is shown below:

import math
from random import randint

def slice_2d_list(my_list, start_row, end_row, start_col, end_col):
    sliced_list = [[my_list[i][j] for j in range(start_col, end_col)] for i in range(start_row, end_row)]
    return sliced_list
def split_matrix(A: list[list[int]]):
    rows = len(A)
    cols = len(A[0])
    rows2 = rows // 2
    cols2 = cols // 2
    a = slice_2d_list(A, 0, rows2, 0, cols2)
    b = slice_2d_list(A, 0, rows2, cols2, cols)
    c = slice_2d_list(A, rows2, rows, 0, cols2)
    d = slice_2d_list(A, rows2, rows, cols2, cols)
    return a, b, c, d

def calculate_max(A, B):
    N = len(A)
    if N == 1 and len(B) == 1:
        return max(A[0], B[0])
    elif N == 1:
        return A[0]
    elif len(B) == 1:
        return B[0]
    maxi: int = 0
    a, b, c, d = split_matrix(A)
    e, f, g, h = split_matrix(B)
    max_1 = calculate_max(a, e)
    max_2 = calculate_max(b, f)
    max_3 = calculate_max(c, g)
    max_4 = calculate_max(d, h)
    maxi = max(max_1, max_2, max_3, max_4)
    return maxi

def matrix_multiply_positive_integer(A, B):
    assert len(A) == len(B), "Matrices must have the same length"
    N = len(A)
    
    maxi = calculate_max(A, B)[0]
    
    M = math.ceil(math.log10(maxi))
    P = math.ceil(math.log10((10**(2*M)-1)*N))
    
    C = []
    D = []
    E = []
    
    for i in range(N):
        C.append(0)
        D.append(0)
        for j in range(N):
            C[i] = C[i] * (10**P) + A[i][j] * (10**M)
            D[i] = D[i] * (10**P) + B[N-1-j][i] * (10**M)
    
    for i in range(N):
        E.append([])
        for j in range(N):
            E[i].append(0)
            E[i][j] = int((C[i] * D[j]) // (10**(P*(N-1)+2*M))) % (10**P)
    
    return E

Because I am very new and I don't know how to measure time complexities, I'm kindly asking: What is the time complexity of the algorithm above? And how can I measure this for other algorithms that I will make in Python?

I have tried to write a matrix multiplication algorithm that could multiply positive integer matrices in sub-cubic time.

ComradeCat
  • 1
  • 1
  • Since this site's objective is to answer specific technical questions and not to provide tutorial services. I suggest you avail yourself of the numerous resources on the web to assist one in determining the time complexity of an algorithms and/or code. [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) is a good starting point. – itprorh66 Jun 10 '23 at 17:54
  • It is not sub-cubic in any way shape or form. Long integer multiplication is **not** free. – n. m. could be an AI Jun 10 '23 at 20:34
  • Since you take n² products of integers that are O(n) in size (which cost O(n log n) even with a recently developed algorithm that is impractical for real life use), this algorithm is slower than cubic. – harold Jun 12 '23 at 22:55

0 Answers0