When an algorithm hasO(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) wherelist[i] == list[j]. Using nested loops will result inO(N²) complexity.

C# Implementation

usingSystem;usingSystem.Collections.Generic;classProgram{staticvoidMain(){List<int>numbers=newList<int>{3,1,4,2,5,3};boolhasDuplicates=HasDuplicatePairs(numbers);Console.WriteLine(hasDuplicates);// Output: True}staticboolHasDuplicatePairs(List<int>numbers){intn=numbers.Count;for(inti=0;i<n;i++){for(intj=i+1;j<n;j++)// Nested loop{if(numbers[i]==numbers[j]){returntrue;}}}returnfalse;}}

Step-by-Step Explanation

1. Outer Loop:

   • Iterates over the list starting from the first element to the last.
   • Executes approximatelyN times, whereN is the size of the list.

2. Inner Loop:

   • For each iteration of the outer loop, the inner loop runs fromj = 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 comparesnumbers[i] andnumbers[j].
   • If a match is found, the method returnstrue.

4. Complexity Analysis:

   • The outer loop runsN times.
   • The inner loop runs an average ofN/2 times for each iteration.
   • Total iterations ≈N * (N - 1) / 2 → Simplifies toO(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

usingSystem;usingSystem.Collections.Generic;classProgram{staticvoidMain(){List<string>words=newList<string>{"listen","silent","enlist","hello","world"};boolhasAnagrams=HasAnagramPairs(words);Console.WriteLine(hasAnagrams);// Output: True}staticboolHasAnagramPairs(List<string>words){intn=words.Count;for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){if(AreAnagrams(words[i],words[j])){returntrue;}}}returnfalse;}staticboolAreAnagrams(stringword1,stringword2){char[]charArray1=word1.ToCharArray();char[]charArray2=word2.ToCharArray();Array.Sort(charArray1);Array.Sort(charArray2);returnnewstring(charArray1)==newstring(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:

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

3. O(N²) Complexity:

   • Sorting within theAreAnagrams method adds anotherO(M log M) complexity (whereM is the length of the word), but for small strings, the overall time complexity is dominated by the nested loops, making itO(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 toO(N × M log M).

Optimized C# Implementation

usingSystem;usingSystem.Collections.Generic;classProgram{staticvoidMain(){List<string>words=newList<string>{"listen","silent","enlist","hello","world"};boolhasAnagrams=HasAnagramPairsOptimized(words);Console.WriteLine(hasAnagrams);// Output: True}staticboolHasAnagramPairsOptimized(List<string>words){HashSet<string>seenAnagrams=newHashSet<string>();foreach(stringwordinwords){char[]charArray=word.ToCharArray();Array.Sort(charArray);stringsortedWord=newstring(charArray);if(seenAnagrams.Contains(sortedWord)){returntrue;}seenAnagrams.Add(sortedWord);}returnfalse;}}

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.