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
-
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.
-
Inner Loop:
- For each iteration of the outer loop, the inner loop runs from
j = i + 1to the end of the list. - This ensures that each pair is checked only once.
- For each iteration of the outer loop, the inner loop runs from
-
Comparison:
- Inside the inner loop, the algorithm compares
numbers[i]andnumbers[j]. - If a match is found, the method returns
true.
- Inside the inner loop, the algorithm compares
-
Complexity Analysis:
- The outer loop runs
Ntimes. - The inner loop runs an average of
N/2times for each iteration. - Total iterations ≈
N * (N - 1) / 2→ Simplifies to O(N²).
- The outer loop runs
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
-
Outer and Inner Loops:
- The outer loop picks a word.
- The inner loop compares it with all subsequent words.
-
Anagram Comparison:
- The
AreAnagramsfunction sorts the characters of both words and compares the results.
- The
-
O(N²) Complexity:
- Sorting within the
AreAnagramsmethod adds another O(M log M) complexity (whereMis the length of the word), but for small strings, the overall time complexity is dominated by the nested loops, making it O(N²).
- Sorting within the
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.
Top comments (0)