Understanding O(N ): Quadratic Time Complexity in C#

When an algorithm has O(N²) complexity, it means the number of operations it performs is proportional to the square of the input size. Nested loops often cause this complexity.

---

Example: Detecting Duplicate Pairs in a List

Problem Statement

We want to check if a list contains duplicate pairs (i, j) where list[i] == list[j]. Using nested loops will result in O(N²) complexity.

C# Implementation

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> numbers = new List<int> { 3, 1, 4, 2, 5, 3 };

        bool hasDuplicates = HasDuplicatePairs(numbers);
        Console.WriteLine(hasDuplicates); // Output: True
    }

    static bool HasDuplicatePairs(List<int> numbers)
    {
        int n = numbers.Count;

        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++) // Nested loop
            {
                if (numbers[i] == numbers[j])
                {
                    return true;
                }
            }
        }

        return false;
    }
}

---

Step-by-Step Explanation

1. Outer Loop:

   • Iterates over the list starting from the first element to the last.
   • Executes approximately N times, where N is the size of the list.

2. Inner Loop:

   • For each iteration of the outer loop, the inner loop runs from j = i + 1 to the end of the list.
   • This ensures that each pair is checked only once.

3. Comparison:

   • Inside the inner loop, the algorithm compares numbers[i] and numbers[j].
   • If a match is found, the method returns true.

4. Complexity Analysis:

   • The outer loop runs N times.
   • The inner loop runs an average of N/2 times for each iteration.
   • Total iterations ≈ N * (N - 1) / 2 → Simplifies to O(N²).

---

A Real-World Example: Checking for Anagrams

Let's extend the concept to a more interesting problem: finding anagrams in a list of strings.

C# Implementation

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<string> words = new List<string> { "listen", "silent", "enlist", "hello", "world" };

        bool hasAnagrams = HasAnagramPairs(words);
        Console.WriteLine(hasAnagrams); // Output: True
    }

    static bool HasAnagramPairs(List<string> words)
    {
        int n = words.Count;

        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (AreAnagrams(words[i], words[j]))
                {
                    return true;
                }
            }
        }

        return false;
    }

    static bool AreAnagrams(string word1, string word2)
    {
        char[] charArray1 = word1.ToCharArray();
        char[] charArray2 = word2.ToCharArray();

        Array.Sort(charArray1);
        Array.Sort(charArray2);

        return new string(charArray1) == new string(charArray2);
    }
}

---

Step-by-Step Explanation

1. Outer and Inner Loops:

   • The outer loop picks a word.
   • The inner loop compares it with all subsequent words.

2. Anagram Comparison:

   • The AreAnagrams function sorts the characters of both words and compares the results.

3. O(N²) Complexity:

   • Sorting within the AreAnagrams method adds another O(M log M) complexity (where M is the length of the word), but for small strings, the overall time complexity is dominated by the nested loops, making it O(N²).

---

Optimization Idea: Using Hashing

To reduce time complexity, you could use a dictionary to store sorted words as keys and their counts as values. This reduces complexity to O(N × M log M).

Optimized C# Implementation

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<string> words = new List<string> { "listen", "silent", "enlist", "hello", "world" };

        bool hasAnagrams = HasAnagramPairsOptimized(words);
        Console.WriteLine(hasAnagrams); // Output: True
    }

    static bool HasAnagramPairsOptimized(List<string> words)
    {
        HashSet<string> seenAnagrams = new HashSet<string>();

        foreach (string word in words)
        {
            char[] charArray = word.ToCharArray();
            Array.Sort(charArray);
            string sortedWord = new string(charArray);

            if (seenAnagrams.Contains(sortedWord))
            {
                return true;
            }

            seenAnagrams.Add(sortedWord);
        }

        return false;
    }
}

---

Conclusion

The quadratic time complexity of O(N²) often arises in naive solutions with nested loops. While simple, these algorithms can become inefficient for large datasets. Optimizing using data structures like hash sets or dictionaries can significantly reduce runtime.