-4

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]
                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

Edit: 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?

james pow
  • 103
  • 2

1 Answers1

0

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).

fgb
  • 1,200
  • 2
  • 6
  • 10
  • On the surface, I'd say this is right, but then it's really O(m * (len(s)/m)) and you are ignoring len(s) in your answer here. len(s) is independent from m by the information given, so I think O(m*n) is still correct and O(n) is not. – user10489 Sep 11 '22 at 21:15
  • @user10489 I'm using the definitions of `n = len(s)` and `m = numRows` from the question. The time depends only on `len(s)` because the `numRows` cancel out. As `numRows` increases, it increases the time for the outer loop and decreases the time for the inner one. – fgb Sep 11 '22 at 23:26
  • numrows does not increase, it is a static variable, nothing in this code changes it; so is col_offset, whose calculation could be lifted out of the loop. I think it is still O(n*m) but I think n is = len(s)/m , which would make this O(len(s)) which I think is what you meant anyway. – user10489 Sep 12 '22 at 02:03