DEV Community

mohamed Tayel
mohamed Tayel

Posted on

1

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs