0

What is the time complexity on the following algorithm?

I am aware that permutations without checking duplicates take O(n!), but I am specifically interested in the shoudSwap function, which is shown below:

// Returns true if str[curr] does not match with any of the 
// characters after str[start] 
bool shouldSwap(char str[], int start, int curr) 
{ 
    for (int i = start; i < curr; i++)  
        if (str[i] == str[curr]) 
            return 0; 
    return 1; 
}
AbsoluteSpace
  • 710
  • 2
  • 11
  • 21
Raghu Karm
  • 9
  • 2
  • complexity is O(curr-start), not O(n). I don't see any n here – mangusta Jul 19 '19 at 22:09
  • @mangusta pls look at the url link included in the post which has all details. Basically shoudSwap called with input range 0 to n. – Raghu Karm Jul 19 '19 at 22:14
  • Important information should not be behind a link, but included in the question. – trincot Jul 19 '19 at 22:15
  • Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Prune Jul 19 '19 at 22:57

1 Answers1

1

If n is the size of the char array str[], then the time complexity of shouldSwap() is O(n) because it will iterate at most once over every element in the str array.

AbsoluteSpace
  • 710
  • 2
  • 11
  • 21