CODEWITHSUNDEEP
algorithmpermutation
Raghu Karm
Raghu Karm

Reputation: 9

Time complexity of this unique permutations algorithm

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

Answers (1)

AbsoluteSpace
AbsoluteSpace

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

Related Questions