As a learning exercise, I am writing a library to evaluate the complexity of an algorithm. I do this by seeing how long the alorgorithm takes for given inputs N, and then do a polynomial regression to see if the algorithm is best fitted by N, N^2, log(N), etc. I wrote Unit Test cases and they seem to work for N^2 and LogN. It's the simplest case, N that is giving me grief. For an order N algorithm, I'm using the following:

```
uint LinearAlgorithm2(uint n)
    {
        uint returnValue = 7;
        for (uint i = 0; i < n; i++)
        {
            //Thread.Sleep(2);
            double y = _randomNumber.NextDouble(); // dummy calculation
            if (y < 0.0005)
            {
                returnValue = 1;
                //Console.WriteLine("y " + y + i);
            }
            else if (y < .05)
            {
                returnValue = 2;
            }
            else if (y < .5)
            {
                returnValue = 3;
            }
            else
            {
                returnValue = 7;
            }

        }
        return returnValue;
    }

```

I have all that nonsense code in there simply because I was concerned that the compiler might have been optimizing my loop away. In any case I think the loop is just a simple loop from 0 to n and therefore this is an algorithm or order N.

My unit test code is:

```
public void TestLinearAlgorithm2()
    {
        Evaluator evaluator = new Evaluator();
        var result = evaluator.Evaluate(LinearAlgorithm2, new List<double>() { 1000,1021, 1065, 1300, 1423, 1599,
            1683, 1691, 1692, 1696, 1699, 1705,1709, 1712, 1713, 1717, 1720,
            1722, 1822, 2000, 2050, 2090, 2500, 2666, 2700,2701, 2767, 2799, 2822, 2877,
            3000, 3100, 3109, 3112, 3117, 3200, 3211, 3216, 3219, 3232, 3500, 3666, 3777,
            4000, 4022, 4089, 4122, 4199, 4202, 4222, 5000 });
        var minKey = result.Aggregate((l, r) => l.Value < r.Value ? l : r).Key;
        Assert.IsTrue(minKey.ToString() == FunctionEnum.N.ToString());
    }

```

And I put the class Evaluator down below. Perhaps before staring at that though I'd ask

1) Do you agree a simple loop 0 to N should be of order N for complexity? I.e. the time to complete the algorithm goes up as n (not nLogn or n^3, etc.)

2) Is there some library code already written to evaluate algorithmic complexity?

3) I'm very suspicious that the problem is one of optimization. Under ProjectSettings->Build in Visual Studio, I have unchecked "Optimize Code". What else should I be doing? One reason I'm suspicious that the compiler is skewing the results is that I print out the times for various input values of n. For 1000 (the first entry) it's 2533, but for 1021 it's only 415! I've put all the results below the Evaluator class.

Thanks for any ideas and let me know if I can provide more info (Github link?) -Dave

Code for Evaluator.cs

```
using MathNet.Numerics.LinearAlgebra;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

/// <summary>
/// Library to evaluate complexity of algorithm.
/// Pass in method and necessary data
/// There are methods to set the size of the test data
/// 
/// Evaluate for LogN, N, NLogN, N^2, N^3, 2^N
/// 
/// Should be able use ideas from
/// https://en.wikipedia.org/wiki/Polynomial_regression
/// to finish problem.  Next need matrix multiplication.
/// Or possibly use this:
/// https://www.codeproject.com/Articles/19032/C-Matrix-Library
/// or similar
/// </summary>
namespace BigOEstimator
{
    public enum FunctionEnum
    {
        Constant = 0,
        LogN = 1,
        N,
        NLogN,
        NSquared,
        NCubed,
        TwoToTheN
    }
    public class Evaluator
    {
        //private List<uint> _suggestedList = new List<uint>();
        private Dictionary<FunctionEnum, double> _results = new Dictionary<FunctionEnum, double>(); 
        public Evaluator()
        {

        }

        public Dictionary<FunctionEnum, double> Evaluate(Func<uint,uint> algorithm, IList<double> suggestedList)
        {
            Dictionary<FunctionEnum, double> results = new Dictionary<FunctionEnum, double>();
            Vector<double> answer = Vector<double>.Build.Dense(suggestedList.Count(), 0.0);
            for (int i = 0; i < suggestedList.Count(); i++)
            {
                Stopwatch stopwatch = new Stopwatch();
                stopwatch.Start();
                var result = algorithm((uint) suggestedList[i]);
                stopwatch.Stop();
                answer[i] = stopwatch.ElapsedTicks;

                Console.WriteLine($"Answer for index {suggestedList[i]} is {answer[i]}");
            }

            // linear case - N
            results[FunctionEnum.N] = CalculateResidual(Vector<double>.Build.DenseOfEnumerable(suggestedList), answer, d => d);
            // quadratic case - NSquared
            results[FunctionEnum.NSquared] = CalculateResidual(Vector<double>.Build.DenseOfEnumerable(suggestedList), answer, d => (d*d));
            // cubic case - NCubed
            results[FunctionEnum.NCubed] = CalculateResidual(Vector<double>.Build.DenseOfEnumerable(suggestedList), answer, d => (d * d * d));
            // NLogN case - NLogN
            results[FunctionEnum.NLogN] = CalculateResidual(Vector<double>.Build.DenseOfEnumerable(suggestedList), answer, d => (d * Math.Log(d)));
            // LogN case - LogN
            results[FunctionEnum.LogN] = CalculateResidual(Vector<double>.Build.DenseOfEnumerable(suggestedList), answer, d => ( Math.Log(d)));

            // following few lines are useful for unit tests. You get this by hitting 'Output' on test!
            var minKey = results.Aggregate((l, r) => l.Value < r.Value ? l : r).Key;
            Console.WriteLine("Minimum Value: Key: " + minKey.ToString() + ", Value: " + results[minKey]);
            foreach (var item in results)
            {
                Console.WriteLine("Test: " + item.Key + ", result: " + item.Value);
            }
            return results;
        }

        private double CalculateResidual(Vector<double> actualXs, Vector<double> actualYs, Func<double, double> transform)
        {

            Matrix<double> m = Matrix<double>.Build.Dense(actualXs.Count, 2, 0.0);
            for (int i = 0; i < m.RowCount; i++)
            {
                m[i, 0] = 1.0;
                m[i, 1] = transform((double)actualXs[i]);
            }
            Vector<double> betas = CalculateBetas(m, actualYs);
            Vector<double> estimatedYs = CalculateEstimatedYs(m, betas);
            return CalculatateSumOfResidualsSquared(actualYs, estimatedYs);

        }
        private double CalculateLinearResidual(Vector<double> actualXs, Vector<double> actualYs)
        {
            Matrix<double> m = Matrix<double>.Build.Dense(actualXs.Count, 2, 0.0);
            for (int i = 0; i < m.RowCount; i++)
            {
                m[i, 0] = 1.0;
                m[i, 1] = (double)actualXs[i];
            }
            Vector<double> betas = CalculateBetas(m, actualYs);
            Vector<double> estimatedYs = CalculateEstimatedYs(m, betas);
            return CalculatateSumOfResidualsSquared(actualYs, estimatedYs);
        }
        private Vector<double> CalculateBetas(Matrix<double> m, Vector<double> y)
        {
            return (m.Transpose() * m).Inverse() * m.Transpose() * y;
        }

        private Vector<double> CalculateEstimatedYs(Matrix<double> x, Vector<double> beta)
        {
            return x * beta;
        }

        private double CalculatateSumOfResidualsSquared(Vector<double> yReal, Vector<double> yEstimated)
        {
            return ((yReal - yEstimated).PointwisePower(2)).Sum();
        }

    }
}

```

Results of one run of unit test (notice discrepancies such as first one!):

```
 Answer for index 1000 is 2533
Answer for index 1021 is 415
Answer for index 1065 is 375
Answer for index 1300 is 450
Answer for index 1423 is 494
Answer for index 1599 is 566
Answer for index 1683 is 427
Answer for index 1691 is 419
Answer for index 1692 is 413
Answer for index 1696 is 420
Answer for index 1699 is 420
Answer for index 1705 is 438
Answer for index 1709 is 595
Answer for index 1712 is 588
Answer for index 1713 is 426
Answer for index 1717 is 433
Answer for index 1720 is 421
Answer for index 1722 is 428
Answer for index 1822 is 453
Answer for index 2000 is 497
Answer for index 2050 is 518
Answer for index 2090 is 509
Answer for index 2500 is 617
Answer for index 2666 is 653
Answer for index 2700 is 673
Answer for index 2701 is 671
Answer for index 2767 is 690
Answer for index 2799 is 685
Answer for index 2822 is 723
Answer for index 2877 is 714
Answer for index 3000 is 746
Answer for index 3100 is 753
Answer for index 3109 is 754
Answer for index 3112 is 763
Answer for index 3117 is 2024
Answer for index 3200 is 772
Answer for index 3211 is 821
Answer for index 3216 is 802
Answer for index 3219 is 788
Answer for index 3232 is 775
Answer for index 3500 is 848
Answer for index 3666 is 896
Answer for index 3777 is 917
Answer for index 4000 is 976
Answer for index 4022 is 972
Answer for index 4089 is 1145
Answer for index 4122 is 1047
Answer for index 4199 is 1031
Answer for index 4202 is 1033
Answer for index 4222 is 1151
Answer for index 5000 is 1588
Minimum Value: Key: NCubed, Value: 5895501.06936747
Test: N, result: 6386524.27502984
Test: NSquared, result: 6024667.62732316
Test: NCubed, result: 5895501.06936747
Test: NLogN, result: 6332154.89282043
Test: LogN, result: 6969133.89207915

```