-2

How would I compute the time complexity of this algorithm? The outer for loop runs n times. The inside for loop runs n-1, n-2, n-3, n-4, ... n-n times after each iteration. 

/*
* isUniqueBrute - This algorithm uses the brute force approach by comparing each character 
* in the string with another. Only a single comparison is made per pair of characters.
*/
bool isUniqueBrute(string str)
{
    char buffer;

    for (int i = 0; i < str.length(); i++)
    {
        for (int j = i+1; j < str.length(); j++)
        {
            if (str[i] == str[j])
                return false;
        }
    }

    return true;
}
Tommy Saechao
  • 1,099
  • 4
  • 17
  • 28
  • see here http://stackoverflow.com/a/526751 – paiv Feb 11 '17 at 19:59
  • 1
    Possible duplicate of [What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?](http://stackoverflow.com/questions/362059/what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop) – Paul Hankin Feb 11 '17 at 20:05

1 Answers1

2

You perform the calculation by doing the math:

outer loop runs n times: O(n)
inner loop runs n-1, n-2, n-3, ... 0 times.

So you break down the iterations:

1 + 1 + 1 + 1 + ... n times  = outer loop
n-1 + n-2 + n-3 + ... n times = inner loop

Rearranging:

1+n-1 = n
1+n-2 = n-1
1+n-3 = n-2
... n times

Add those up, and you get the sum of all numbers from 1..n. I'm sure you know the formula by now, but:

n * (n+1) / 2

Which, if you expand it, includes n² as the dominant element. So this function is O(n²).

aghast
  • 14,785
  • 3
  • 24
  • 56