CODEWITHSUNDEEP
javascriptalgorithm
Max Koretskyi
Max Koretskyi

Reputation: 105497

Can't define better algorithm using complexity metric

I need to write an algorithm that checks for uniqueness of a character within a string. I've written the following algorithm:

function unique(s) {
    for (var i=0; i<s.length-1; i++) {
        for (j=i+1; j<s.length; j++) {
            if (s[i] === s[j]) {
                return false;
            }
        }
    }
    return true;
}

When calculating the number of operations for the worst case scenario, the formula is

n/2x(n-1)=(n^2-n)/2

and the complexity O(n)=n^2.

Now, I may have written the following algorithm which is not optimized:

function unique(s) {
    for (var i=0; i<s.length; i++) {
        for (j=0; j<s.length; j++) {
            if ((s[i] === s[j]) && (i!==j)) {
                return false;
            }
        }
    }
    return true;
}

but it gives the same 0(n)=n^2. So it seems that I can't tell which algorithm is better based on the 0(n) - is it correct? So why use 0(n)? And what metric can show that the first algorithm is better than the second one?

Upvotes: 2

Views: 54

Answers (3)

Paul Hankin
Paul Hankin

Reputation: 58271

Your algorithms are O(n), not O(n^2), despite appearances.

s is a string, and characters are limited to 16 bits. That means the outer loop will execute at most 65536 times, and this maximum case can only happen if the string is exactly 65536 characters long, and contains each code point exactly once.

With this observation, you can create an O(1) solution. Simply add an initial check to see if the string is longer than 65536 characters, and if it is then immediately return true. If it's not, then use either of your algorithms to check the string for duplicates.

Upvotes: 2

kraskevich
kraskevich

Reputation: 18556

The O notation is used for analyzing the asymptotic behavior of the algorithm, not a precise number of operations(yes, both algorithms are the same with respect to this notation).

If you want to show that the first algorithm is better, you can use the number of pairs characters compared (or the total number of loop iterations) as a metric.

Upvotes: 1

GhostCat
GhostCat

Reputation: 140457

You want to use a data structure that tells if a certain element is already given within that data structure.

Like a hashtable. By adding all chars of your word into that table one by one, you can easily check if that "to be added" char is already in. So you avoid the n * n complexity of comparing each character with each other character in your table.

Upvotes: 0

Related Questions