# What is the big O of this algorithm? [duplicate]

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?

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

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)`.
• @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.