SprialPrint - Answer Check - Time O(n) and Space Complexity O(1)

#1

Hi TA,

I am learning about TIme Complexity. Is my answer correct? I think the overall TimeCompleixty O(n) and space is O(1) - since it only uses stack memory space. Please correct me if my answer is incorrect. Thanks.

1368×851 111 KB
i

#2

hey @sumyatkw
Time Complexity: O(mn).
To traverse the matrix O(mn) time is required.

#3

Time Complexity
I have got the following 3 questions.

  1. May I know why it is O(mn)?

        What does m refers to here? Is me i for row?
    n for column?

  2. Does it mean that in general it is O(n^2)??

  3. How about space complexity?

Thanks.

#4

Q. What does m refers to here? Is me i for row?
n for column?
Answer : yes
Q2. Does it mean that in general it is O(n^2)??
answer if n==m , otherwise O(M*N)
Q3. How about space complexity?
Space Comepxlity: O(1).
No extra space is required.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#5

Thanks for your prompt reply.

I just want to clarify Q2.
Q2 - O(m*n) is roughly equivalant to O(n^2) or O(n)??

Q3 - Space complexity. In this problem, the only object created is the array and is stored in heap. Other than that, no extra additional space is used, this is why it is O(1). Is my understanding correct?

Thanks.

#6

Q2. O(m*n) is roughly equivalant to O(n^2) or O(n)??
Answer : roughly you can say O(N^2)
No extra space is required. Space Comepxlity: O(1).// that Means Constant Space .

#7

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.