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

4
  • 1
    Show your work as to what you have figured out so far. Can you identify looping in the algorithm?
    – Erik Eidt
    Sep 10, 2022 at 22:58
  • edited to show the work @ErikEidt
    – james pow
    Sep 10, 2022 at 23:40
  • What does this code do? Sep 11, 2022 at 0:24
  • This is buggy if len(s)<numrows*4-1 or something like that
    – user10489
    Sep 11, 2022 at 2:06

1 Answer 1

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

3
  • 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, 2022 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, 2022 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, 2022 at 2:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.