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

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