C# SortedSet Time Complexity

In C#, the SortedSet<T> class is a collection that maintains unique elements in sorted order. Its internal structure, a balanced binary search tree, ensures that elements are always sorted and allows efficient set operations. This article examines the time complexity of various operations on SortedSet<T>, providing practical examples and comparisons to help you understand and use this collection effectively.

Internal Structure and Complexity

SortedSet<T> uses a Red-Black Tree, a balanced binary search tree. This structure provides logarithmic time complexity for insertion, deletion, and lookup.

Time Complexity of Common Operations

Insertion (Add): O(log n)

Adding an element requires maintaining the tree's balance.

Deletion (Remove): O(log n)

Removing an element requires a tree re-balance.

Search (Contains): O(log n)

Checking if an element exists leverages the binary search tree structure.

Enumeration: O(n)

Iterating through the set requires traversing all nodes.

Set Operations (Union, Intersection, Difference):

UnionWith: O(n + m), where n and m are the sizes of the two sets.
IntersectWith: O(n + m)
ExceptWith: O(n + m)

Practical Examples of Operations

Adding and Removing Elements

using System;
using System.Collections.Generic;

public class SortedSetExample
{
    public static void Main()
    {
        // Create a SortedSet of integers
        SortedSet<int> numbers = new SortedSet<int> { 10, 20, 30, 40, 50 };

        // Add a new number
        numbers.Add(35);
        Console.WriteLine("After adding 35:");
        DisplaySet(numbers);

        // Remove an existing number
        numbers.Remove(20);
        Console.WriteLine("After removing 20:");
        DisplaySet(numbers);
    }

    // Helper method to display elements in a SortedSet
    public static void DisplaySet(SortedSet<int> set)
    {
        foreach (int number in set)
        {
            Console.WriteLine(number);
        }
    }
}

Searching for Elements

using System;
using System.Collections.Generic;

public class SortedSetSearchExample
{
    public static void Main()
    {
        // Create a SortedSet of strings
        SortedSet<string> fruits = new SortedSet<string> { "Apple", "Banana", "Cherry", "Date", "Fig" };

        // Check if an element is present
        string target = "Banana";
        bool isPresent = fruits.Contains(target);
        Console.WriteLine($"Is {target} present in the SortedSet? {isPresent}");

        // Check for a non-existing element
        target = "Grape";
        isPresent = fruits.Contains(target);
        Console.WriteLine($"Is {target} present in the SortedSet? {isPresent}");
    }
}

Set Operations

using System;
using System.Collections.Generic;

public class SortedSetOperationsExample
{
    public static void Main()
    {
        // Create two SortedSets
        SortedSet<int> set1 = new SortedSet<int> { 1, 2, 3, 4, 5 };
        SortedSet<int> set2 = new SortedSet<int> { 3, 4, 5, 6, 7 };

        // Perform a union operation
        set1.UnionWith(set2);
        Console.WriteLine("Union of Set1 and Set2:");
        foreach (int number in set1)
        {
            Console.WriteLine(number);
        }

        // Perform an intersection operation
        set1.IntersectWith(set2);
        Console.WriteLine("Intersection of Set1 and Set2:");
        foreach (int number in set1)
        {
            Console.WriteLine(number);
        }
    }
}

Conclusion

SortedSet<T> in C# offers efficient performance for various operations by leveraging a balanced tree structure. By understanding its time complexity and practical applications, you can better manage sorted and unique collections in your applications.

c# sortedset time complexity