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

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

1 Answer 1

Reset to default
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).

Improve this answer
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
    Commented 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
    Commented 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
    Commented Sep 12, 2022 at 2:03

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