I think it’s O(m*n) but someone said it’s O(n). If you think it’s O(n) could you provide an explanation?
def convert(self, s: str, numRows: int) -> str: if numRows == 1: return s res = "" for i in range(numRows): col = i while col < len(s): res += scol_offset = 2 * (numRows - 1) col_next = col + col_offset diag = col + 2 * (numRows - 1 - col % col_offset) if diag != col_next and diag != col and diag < len(s): res += s[diag] col = col_next return res
Representing outer loop:
m. and for the inner loop I’m representing
n. For each iteration of
m there is
n. Therefore I think the time complexity is
O(mn). Is this correct?
As the inner loop increments
2 * (numRows - 1) each time until its above
n, its time complexity is
O(n/m). Doing this
m times would give a total time complexity of