String reverse operation best time complexity: Is it O(n) or O(n/2)?

Question

Below code snippet for String reverse

private static String reverseString(String originalString){
char arr[]= originalString.toCharArray();
char temp;

for(int i= 0,j=arr.length-1;i<(arr.length/2);i++,j--){

 temp=arr[i];
 arr[i]=arr[j];
 arr[j]=temp;
}
return new String(arr);

I have seen lot of discussion over the time complexity for the above String reverse where some have mentioned the complexity to be O(n/2) and some O(n).

I would like to understand which one would actually be the correct time complexity for the string reverse.

Any insight would be really helpful in assuaging the confusion here.

Answer 1

Asymptotically there is no difference between O(n) and O(n/2). The difference between the two is constant.

If you want to compute the exact number of operations in the above code snippet, it would be more accurate to say it's 3n/2, since each iteration of the loop contains 3 operations. Of course you'll also have to add the conversion of the input String to a char array and vice versa, both of which also take linear time.

Answer 2

Big O notation is used in the asymptotic analysis ( meaning in the long run )

This means that your all linear functions will have the same time complexity that is O(n), It does not matter that T(n) = n/1 or n/2 or n/3 because in the long run they will all have the same effect.