algorithms.py

matrix = [[1, 2, 3, 4],
          [5, 6],
          [],
          [7, 8, 9]]
	

# O(n)
# Выполняется цикл, кол-во итераций = кол-ву элементов матрицы + кол-во пустых строк.
# Если элементы строки кончились, начинает обрабатываться след. строка.
# Для каждой пустой строки предусмотрена отдельная итерация, которая совершает переход на новую строку
#
# Параметры:
# function --- операция над элементом матрицы
# matrix --- двумерная матрица
def big_oh_n(function, matrix):
	side1_len = len(matrix)
	
	side1_index = 0
	side2_index = 0
	
	# Кол-во значений в матрице + кол-во пустых строк. 
	# Сложность O(n)
	iterations_count = sum(list(map(lambda row: len(row) if len(row) != 0 else 1, matrix)))
	
	# Оператор индексации и len имеют сложность O(1)
	side2_len = len(matrix[side1_index])
	
	for i in range(iterations_count): # O(iterations_count) = O(кол-во элементов в матрице + кол-во пустых строк)
		if (side2_index >= side2_len): # элементы строки закончились
			side1_index += 1
			side2_len = len(matrix[side1_index])
			
			if (side2_len == 0): # пустая строка
				continue
			
			side2_index = 0
				
		function(matrix[side1_index][side2_index])
		
		side2_index += 1
		


big_oh_n(print, matrix)