1
$\begingroup$

I am new to asymptotic analysis, on solving the array rotation problem on geeksforgeeks the first solution provided was using a temporary array, I tried implementing this logic and found that the space complexity is O(m) where m is the number of times the array needs to be rotated. But the time complexity is given as O(n) where n is the size of the array. But I found that the time complexity should be O(n+m)

Input arr[] = [1, 2, 3, 4, 5, 6, 7], m = 2, n =7
1) Store d elements in a temp array 
 temp[] = [1, 2] // It takes m iterations to copy the array
2) Shift rest of the arr[]
 arr[] = [3, 4, 5, 6, 7, 6, 7] // n-m iteration for shifting
3) Store back the d elements
 arr[] = [3, 4, 5, 6, 7, 1, 2] // m iterations for storing the elements back

Here is how I calculated time complexity

=> m+(n-m)+m
=> O(n+m)

Can anyone help me to figure out what I am doing wrong?

asked Jul 23, 2019 at 16:00
$\endgroup$

1 Answer 1

2
$\begingroup$

$O(n+m)$ and $O(n)$ are the same. $m$ can never be more than $n$, so $n+m\leq 2n =O(n)$.

answered Jul 23, 2019 at 16:34
$\endgroup$

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.