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 += s
col_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

My solution:
Representing outer loop: range(numRows) by m. and for the inner loop I’m representing len(s) by 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 col by 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 O(n).


Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *