BenchmarkDotNet: DOTNET Lab & Demo

ComplexityBenchmarks.cs

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Order;
using System;
using System.Linq;

namespace BenchmarkDotNetLab
{
    [MemoryDiagnoser]
    [Orderer(SummaryOrderPolicy.FastestToSlowest)]
    [RankColumn]
    public class ComplexityBenchmarks
    {
        // We'll vary N to see scaling
        [Params(100, 500, 1_000)]
        public int N;

        private int[] _data = null!;

        [GlobalSetup]
        public void Setup()
        {
            _data = Enumerable.Range(0, N).ToArray();
        }

        // O(N): Linear scan
        [Benchmark(Baseline = true)]
        public int LinearScan()
        {
            int sum = 0;
            var data = _data;
            for (int i = 0; i < data.Length; i++)
            {
                if (data[i] % 2 == 0)
                    sum++;
            }
            return sum;
        }

        // O(N^2): Pair comparison
        [Benchmark]
        public int Quadratic_ParityPairs()
        {
            int count = 0;
            var data = _data;
            for (int i = 0; i < data.Length; i++)
            {
                for (int j = i + 1; j < data.Length; j++)
                {
                    if (((data[i] + data[j]) & 1) == 0)
                        count++;
                }
            }
            return count;
        }
    }
}