Reputation: 9
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;
}
Upvotes: 0
Views: 121
Reputation: 770
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.
Upvotes: 1