Optimizing this C algorithm

algorithm

optimization

programming

software development

Optimizing this C algorithm

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Algorithms Complexity & Performance C# & .NET

Introduction

Optimizing C# algorithms involves identifying bottlenecks and applying targeted improvements: choosing better data structures, reducing allocations, eliminating redundant computation, and leveraging language-specific features like Span<T> and LINQ. This article walks through common optimization techniques with practical examples.

Profiling Before Optimizing

Always measure before optimizing. Use Stopwatch for quick benchmarks and BenchmarkDotNet for rigorous comparisons:

csharp

1using System.Diagnostics;
2
3var sw = Stopwatch.StartNew();
4int result = SlowAlgorithm(data);
5sw.Stop();
6Console.WriteLine($"Elapsed: {sw.ElapsedMilliseconds}ms");

For production profiling, use BenchmarkDotNet:

csharp

1using BenchmarkDotNet.Attributes;
2using BenchmarkDotNet.Running;
3
4[MemoryDiagnoser]
5public class AlgorithmBenchmarks
6{
7    private int[] data;
8
9    [GlobalSetup]
10    public void Setup() => data = Enumerable.Range(0, 100_000).ToArray();
11
12    [Benchmark(Baseline = true)]
13    public int Original() => SlowSum(data);
14
15    [Benchmark]
16    public int Optimized() => FastSum(data);
17}
18
19BenchmarkRunner.Run<AlgorithmBenchmarks>();

Optimization 1: Replace O(n²) with O(n)

The most impactful optimization is reducing algorithmic complexity:

csharp

1// O(n²) — checking all pairs for duplicates
2public static bool HasDuplicatesSlow(int[] arr)
3{
4    for (int i = 0; i < arr.Length; i++)
5        for (int j = i + 1; j < arr.Length; j++)
6            if (arr[i] == arr[j])
7                return true;
8    return false;
9}
10
11// O(n) — using a HashSet
12public static bool HasDuplicatesFast(int[] arr)
13{
14    var seen = new HashSet<int>(arr.Length);
15    foreach (int x in arr)
16        if (!seen.Add(x))
17            return true;
18    return false;
19}

Optimization 2: Choose the Right Data Structure

csharp

1// Slow: searching a List<T> is O(n)
2List<string> list = GetLargeList();
3bool found = list.Contains("target");  // O(n)
4
5// Fast: HashSet<T> lookup is O(1)
6HashSet<string> set = new HashSet<string>(list);
7bool found = set.Contains("target");   // O(1)

Operation	`List<T>`	`HashSet<T>`	`Dictionary<K,V>`	`SortedSet<T>`
Search	O(n)	O(1)	O(1)	O(log n)
Insert	O(1)*	O(1)	O(1)	O(log n)
Delete	O(n)	O(1)	O(1)	O(log n)
Ordered	Yes	No	No	Yes

Optimization 3: Reduce Allocations

Excessive object allocation increases GC pressure. Use value types, Span<T>, and pooling:

csharp

1// Bad: allocates a new string for every substring check
2public static int CountSubstrings(string text, string target)
3{
4    int count = 0;
5    for (int i = 0; i <= text.Length - target.Length; i++)
6    {
7        if (text.Substring(i, target.Length) == target)  // Allocates!
8            count++;
9    }
10    return count;
11}
12
13// Good: use Span<T> to avoid allocations
14public static int CountSubstringsOptimized(string text, string target)
15{
16    int count = 0;
17    ReadOnlySpan<char> textSpan = text.AsSpan();
18    ReadOnlySpan<char> targetSpan = target.AsSpan();
19
20    for (int i = 0; i <= textSpan.Length - targetSpan.Length; i++)
21    {
22        if (textSpan.Slice(i, targetSpan.Length).SequenceEqual(targetSpan))
23            count++;
24    }
25    return count;
26}

Optimization 4: Cache Computed Values

csharp

1// Bad: recomputes expensive operation every iteration
2for (int i = 0; i < items.Length; i++)
3{
4    double threshold = Math.Sqrt(items.Length) * ComputeFactor();  // Constant!
5    if (items[i] > threshold) Process(items[i]);
6}
7
8// Good: compute once outside the loop
9double threshold = Math.Sqrt(items.Length) * ComputeFactor();
10for (int i = 0; i < items.Length; i++)
11{
12    if (items[i] > threshold) Process(items[i]);
13}

Optimization 5: Use Array/Span over LINQ for Hot Paths

LINQ is readable but adds overhead from delegates and allocations:

csharp

1// LINQ — readable but allocates iterators and delegates
2int sum = numbers.Where(n => n > 0).Sum();
3
4// Manual loop — no allocations, faster in tight loops
5int sum = 0;
6foreach (int n in numbers)
7{
8    if (n > 0) sum += n;
9}
10
11// Span + for loop — fastest for arrays
12int sum = 0;
13Span<int> span = numbers.AsSpan();
14for (int i = 0; i < span.Length; i++)
15{
16    if (span[i] > 0) sum += span[i];
17}

Optimization 6: StringBuilder for String Concatenation

csharp

1// Bad: O(n²) — creates a new string on each concatenation
2string result = "";
3for (int i = 0; i < 10000; i++)
4    result += i.ToString() + ",";
5
6// Good: O(n) — StringBuilder mutates in place
7var sb = new StringBuilder(10000 * 5);  // Pre-allocate capacity
8for (int i = 0; i < 10000; i++)
9{
10    sb.Append(i);
11    sb.Append(',');
12}
13string result = sb.ToString();

Optimization 7: Parallel Processing

For CPU-bound work on large datasets, use Parallel.For or PLINQ:

csharp

1// Sequential
2double[] results = new double[data.Length];
3for (int i = 0; i < data.Length; i++)
4    results[i] = ExpensiveComputation(data[i]);
5
6// Parallel
7Parallel.For(0, data.Length, i =>
8{
9    results[i] = ExpensiveComputation(data[i]);
10});

Common Pitfalls

Premature optimization: Optimize only after profiling identifies the actual bottleneck. Most code runs infrequently enough that readability matters more than micro-performance.
Micro-benchmarking mistakes: JIT compilation, CPU caching, and GC pauses skew naive benchmarks. Use BenchmarkDotNet with warmup iterations for reliable measurements.
LINQ in hot loops: LINQ is fine for cold paths. In tight loops called millions of times, the delegate invocation and iterator allocation cost adds up. Switch to for loops in hot paths.
Boxing with generics: Using object or non-generic interfaces with value types causes boxing. Prefer generic methods and interfaces (IComparable<T> over IComparable).
Over-parallelizing: Parallel processing has thread management overhead. For small datasets or cheap operations, the overhead exceeds the benefit. Only parallelize CPU-bound work on large inputs.

Summary

Profile first with Stopwatch or BenchmarkDotNet — never guess the bottleneck
Reduce algorithmic complexity (O(n²) → O(n)) before micro-optimizing
Choose appropriate data structures: HashSet for lookups, Dictionary for key-value, Span<T> for slicing without allocation
Minimize allocations in hot paths using Span<T>, StringBuilder, and value types
Use Parallel.For for CPU-bound work on large datasets, but avoid over-parallelizing

DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course

Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Optimizing this C algorithm

Data Structures & Algorithms practice on Codemia

Introduction

Profiling Before Optimizing

Optimization 1: Replace O(n²) with O(n)

Optimization 2: Choose the Right Data Structure

Optimization 3: Reduce Allocations

Optimization 4: Cache Computed Values

Optimization 5: Use Array/Span over LINQ for Hot Paths

Optimization 6: StringBuilder for String Concatenation

Optimization 7: Parallel Processing

Common Pitfalls

Summary

Related reading

DSA Fundamentals

Track what you have practised

Data Structures & Algorithms practice on Codemia