CODEWITHSUNDEEP
c++time-complexity
Dev5
Dev5

Reputation: 459

What is the time complexity of this C++ code

I am just beginning to learn about time complexities, how do I find the time complexity of the following code

vector<int> nums = {3,2,4,5,1,6,7,1,8,2,6,9} //say size n;
int j = 0;
for(int i=n-1;i>j;i--)
{
    if(nums[i]>nums[j])
    {
         swap(nums[i],nums[j]); //simple swap function
         reverse(nums.begin()+j+1,nums.end());  //std::reverse function from STL
         return;
     }
}

When considering the loop alone, the time complexity would be O(n). But what about considering the functions inside and the return. I would like to know how it affects the time complexity.
Any help is appreciated, thanks

Upvotes: 0

Views: 234

Answers (2)

WhozCraig
WhozCraig

Reputation: 66194

This is O(N).

  • In the ideal case, where every value holds false that num[i] > num[0], the for loop will iterate the sequence, no swaps nor reversal will take place, and you're done. O(N).
  • In the case where any pairing leads to num[i] > num[0] being true, you will swap one pair (O(1)), iterate the remaining sequence and reverse them (O(N)), and again, you're done with that hard return;.

I.e., this is O(N).

Upvotes: 3

Laiba Abid
Laiba Abid

Reputation: 71

The swap function is essentially O(1) as its a set number of operations to swap two indices. The reverse function on the other hand is O(n) as it traverses the entire array to reverse it as shown by the documentation

So given that you are reversing your array n times (assuming j can be 0 in for loop), i'd say your complexity comes up to O(n^2)if you didn't have the return statement.

With the return statement, you are not reversing your array in each iteration but only once after which you exit. So O(n)(for loop) + O(n)(reverse) = O(n)

Upvotes: 2

Related Questions