How to calculate time complexity of this function which checks if a string has all unique characters?

Question

The book "Cracking the Coding Interview", and this Stack Overflow question discusses a function which determines if a string contains all unique characters. The book's answer which uses bit shifting is in the question link ( please see the top answer on the page) and I won't repeat it here.

The Java answer has a O(N) complexity, and I can't get my head around what O(N) actually means. I actually want to find out what is the time complexity for this implementation that I wrote just now. Is it O(N) ? How does one figure the complexity?

static void Main(string[] args)
    {
        string stringToCheck ;
        bool hasAllUniqueChars = false;
        stringToCheck = "Test";

        hasAllUniqueChars = CheckForUniqueChars(stringToCheck);

        Console.WriteLine("String is Unique {0}", hasAllUniqueChars);
        Console.Read();
    }

    private static bool CheckForUniqueChars(string stringToCheck)
    {
        for (int i = 0; i < stringToCheck.Length - 1; i++)
        {
            for (int j = i; j < stringToCheck.Length - 1; j++)
            {
                if (Char.ToUpper(stringToCheck.ElementAt(i)) == 
                    Char.ToUpper(stringToCheck.ElementAt(j+1)))
                {
                    return false;
                }
            }
        }
        return true;           

    }

This returns false for Test,test,Hello, and true for SuperMan,SpiderMan and Sponge and works fine.

Thank you

Your method is actually *O(n^3)* (because `string.ElementAt` makes another loop inside). Read more about Big O notation on wikipedia: http://en.wikipedia.org/wiki/Big_O_notation — MarcinJuraszek, Aug 20 '13 at 18:11
[A Beginner's Guide to Big O Notation](http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/) — Jim Mischel, Aug 20 '13 at 18:13
This question appears to be off-topic because it is about Big O notation — Tim S., Aug 20 '13 at 18:14
@MarcinJuraszek That is not another loop. It is just comparison using indices from the 2 loops. — paparazzo, Aug 20 '13 at 18:16
@Blam Yes it is, but it not simple array lookup. `ElementAt()` method is *O(n)* on `IEnumerable`, so whole method is *O(n^3)*, isn't it? (`ElementAt` is *O(1)* on `IList`, but `string` does not implement `IList`). Check this: [Is string.ElementAt() O(1)?](http://stackoverflow.com/questions/4318260/is-string-elementat-o1) — MarcinJuraszek, Aug 20 '13 at 18:17
There are two different things here. Your *algorithm* is quadratic (O(N^2)). Your *implementation* is cubic (O(N^3)) (but doesn't need to be). — Asad Saeeduddin, Aug 20 '13 at 18:25

score 6 · Answer 1 · answered Aug 20 '13 at 18:32

Your algorithm is O(n^2), or to be more accurate - could be O(n^2). Could be, because right now it's O(n^3).

ElementAt() method is O(n) on IEnumerable, so because it's executed within two nested loops whole method is O(n^3).

You could do it O(n^2) by transforming strings into char[] before loops and using array indexer instead of ElementAt extension method:

private static bool CheckForUniqueChars(string stringToCheck)
{
    var chars = stringToCheck.ToCharArray();
    for (int i = 0; i < stringToCheck.Length - 1; i++)
    {
        for (int j = i; j < stringToCheck.Length - 1; j++)
        {
            if (Char.ToUpper(chars[i]) == Char.ToUpper(chars[j+1]))
            {
                return false;
            }
        }
    }
    return true;           
}

Bonus: another O(n) approach (because HashSet<T> lookup is O(1)):

private static bool CheckForUniqueChars(string stringToCheck)
{
    var characters = new HashSet<char>();

    foreach (var character in stringToCheck)
        if (!characters.Add(character))
            return false;

    return true;
}

Thanks! I found your detailed answer very informative.And learnt something new . +1 — iAteABug_And_iLiked_it, Aug 20 '13 at 19:04

Bart van Nierop · Accepted Answer · 2013-08-20T18:59:44.757

The notation O(N) is called Big O Notation. What it provides is an upper bound of the amount of (primitive) operations that an algorithm requires relative to the size of its input. The size of the input is often denoted as N.

If the amount of primitive operations is independent of the input size, then the complexity of the algorithm is O(1), or constant time.

If the amount of primitive operations grows linearly as N grows (ie: when N doubles, so does the amount of operations) then the time complexity is linear, or O(N).

In your example, the upper bound appears to be O(N^2) to the casual reader:

for (each item in input)
  for (each item in input)
    // do something

When N is doubled, the amount of operations quadruples.

However, because the time complexity of ElementAt is linear and not constant, the complexity is actually O(N^3).

Thank you! Marcin's answer was very informative too, if Icould accept both I would have. But my question was actually to find out how to figure the time complexity , and to get an easy to understand explanation. This is what I was after. +1 — iAteABug_And_iLiked_it, Aug 20 '13 at 19:05

paparazzo · Answer 3 · 2013-08-20T18:58:29.447

1

Not an answer to the O(?)

But this is close to O(N) as HashSet should be close to O(1) for this.
Note HashSet.Count is O(1).

HashSet<char> chars = new HashSet<char>();
string password = "password";
Int32 count = 0;
char cUpper;
foreach (char c in password)
{
    count++;
    cUpper = char.ToUpper(c);
    if (!chars.Add(char.ToUpper(c))) 
    {
        System.Diagnostics.Debug.WriteLine("not uniue");
        break;
    }
}
if(count == chars.Count) System.Diagnostics.Debug.WriteLine("uniue");

+1 Did not see that Marcin had this answer minus the ToUpper
ToUpper is better to use than ToLower but I forget why
String has a case insensitive comparison but char does not

edited Aug 20 '13 at 18:58

answered Aug 20 '13 at 18:49

paparazzo

44,497
23
105
176

I don't see a reason why `ToUpper` would be "better to use" than `ToLower`. That's nonsense. Not to mention that OP didn't ask for case insensitive comparison. – vgru Aug 21 '13 at 06:10
@Groo Code posted by OP uses a ToUpper comparison. Not all characters have an upper and lower case. – paparazzo Aug 21 '13 at 12:38
That's correct, they don't, but I still don't see a reason not to use `ToLower()`. – vgru Aug 21 '13 at 12:43
@Groo And you did not see the ToUpper in OP question. If you want to use ToLower then do so. – paparazzo Aug 21 '13 at 12:55
Yes, OP used `ToUpper`, but I am not really sure if he indented to, or understood why it's even there since it's not specified in neither his question nor the linked thread. And sure, I might use `ToLower` if the problem requires case-insensitivity, but isn't *ToUpper better to use than ToLower*? – vgru Aug 21 '13 at 13:00
Really OP used a case insensitive comparison but that is irrelevant because you don't know if that was intentional. Go away. – paparazzo Aug 21 '13 at 13:16
Ok, I'm "going away", but I am afraid my comments will stick around to indicate to other users that your answer contains an incorrect statement. I can't say the answer is otherwise "not useful" so I didn't downvote it, but it's funny you have such a defending attitude towards something without even trying to back it up (for me, for yourself or others). – vgru Aug 21 '13 at 14:35
@Groo From the beginning my answer included "but I forget why". Expect me to recall something I forgot is about as reasonable as posted code from OP is not relevant. – paparazzo Aug 21 '13 at 14:51

Phillip Carter · Answer 4 · 2013-08-20T18:31:19.583

0

Edit: It's O(n^3), or proportional in growth to a third-order polynomial, as per the suggestions of other users. This is because ElementAt() loops through the string.

The key to this complexity is in your iteration. This structure:

for (each item in this thing)
{
   for(each item in this thing)
   {
      if (iterate through this thing to check a condition)
   }
}

Is going to have an order of growth proportional to a third-order polynomial. It's not as bad as other routines like this because the inner iteration via the inner loop gets smaller as you increment, but you're still iterating for every element of the string, and iterating across the string for each of those iterations. Chances are if your algorith is O(n^3), you could stand to refactor it.

Sans the ElementAt() call, it's very similar to Selection Sort with how it iterates, if you're interested.

edited Aug 20 '13 at 18:31

answered Aug 20 '13 at 18:17

Phillip Carter

4,895
16
26

2

`ElementAt()` makes another loop inside. – MarcinJuraszek Aug 20 '13 at 18:17
Yes indeed it does. Revising, since this is now a third-order polynomial. – Phillip Carter Aug 20 '13 at 18:24
@MarcinJuraszek The implementation could easily be changed to be O(N^2). – Asad Saeeduddin Aug 20 '13 at 18:26
@Asad Yes, just two `ToCharArray()` calls. However, current implementation is *O(n^3)*. – MarcinJuraszek Aug 20 '13 at 18:27
@MarcinJuraszek I know. Could you please post what you've highlighted in comments above as an answer? – Asad Saeeduddin Aug 20 '13 at 18:28
@Asad I did. However, still things the question is a little bit off-topic here. – MarcinJuraszek Aug 20 '13 at 18:32
There is no such thing as a *good* or *bad* O(n) complexity. The fact that the inner loop starts at `i` doesn't reduce the complexity. – vgru Aug 20 '13 at 18:43
@Groo I don't mention that it reduces complexity. – Phillip Carter Aug 20 '13 at 18:51
@Edgy *It's not as bad as other routines like this because the inner iteration via the inner loop gets smaller as you increment*. The algorithm is O(n^2), and that's bad as any other O(n^2) algorithm. – vgru Aug 20 '13 at 19:30
@Groo Not in practice, no. In almost every timed case it will run faster than a naiive O(n^2) algorithm. They share the same order of growth, but they absolutely will not share the same runtime. – Phillip Carter Aug 20 '13 at 21:14

How to calculate time complexity of this function which checks if a string has all unique characters?

4 Answers4