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?

$\endgroup$
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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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