testing program for verifying linear algorithm compared to quadratic algorithm for roslyn issue 13685: https://github.com/dotnet/roslyn/issues/13685

Program.cs

using System;
using System.Collections.Generic;
using System.Linq;
using Combinatorics.Collections;

namespace ConsoleApp1
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var fails = 0;
            for (var i = 2; i < 5; i++)
            {
                //need to generate all possible directed graphs with at least 1 edge and i nodes
                var nodes = Enumerable.Range(0, i).ToArray();
                var potentialedges = new Variations<int>(nodes, 2).ToArray();

                for (var edgeCount = 1; edgeCount < potentialedges.Length; edgeCount++)
                {
                    foreach (var edgeSet in new Combinations<IList<int>>(potentialedges, edgeCount))
                    {
                        if(!CompareAlgorithms(CreateCandidatesListFromGraph(nodes, edgeSet)) && fails++==10)
                        {
                            Console.ReadKey();
                            fails = 0;
                        }
                    }
                }
            }
        }

        private static Func<List<Candidate>> CreateCandidatesListFromGraph(int[] nodes, IList<IList<int>> edgeSet)
        {
            return () => {
                var c =
                    nodes.Select(
                            ix =>
                                new Candidate
                                {
                                    Signature = new Signature { Name = new string((char)('A' + ix), 1) }
                                })
                        .ToList();
                foreach (var edge in edgeSet)
                {
                    c[edge[0]].Signature.MakeBatterThan(c[edge[1]].Signature);
                }
                return c;
            };
        }

        private static bool CompareAlgorithms(Func<List<Candidate>> candidateListGenerator)
        {
            var c = candidateListGenerator();
            GetQuadraticResults(c);
            var applicable = c.Where(ci => ci.Kind == OperatorAnalysisResultKind.Applicable).Select(ci => ci.Signature.Name).ToArray();
            var result = string.Join(",", applicable);

            //spec breaking: spec says all must be compared and it is ambiguous if there is not exactly 1 best candidate
            //current optimizations are not correct if there are 0 best...
            if (applicable.Length != 1) return true;

            var c2 = candidateListGenerator();
            Optimizations(c2);
            var result2 = string.Join(",",
                c2.Where(ci => ci.Kind == OperatorAnalysisResultKind.Applicable).Select(ci => ci.Signature.Name));

            if (result != result2)
            {
                var option = candidateListGenerator();
                Console.WriteLine(string.Join("; ", option));
                Console.WriteLine("old: {1}\nnew: {2}\n", result == result2, result, result2);
            }
            return result == result2;
        }


        public static void GetLinearResults2(List<Candidate> candidates)
        {
            object useSiteDiagnostics = new object();
            object right = null;
            object left = null;


            //???

        }
        public static void Optimizations(List<Candidate> candidates)
        {
            object useSiteDiagnostics = new object();
            object right = null;
            object left = null;

            if (candidates.Count < 2) return;
            //optimization 1: no need to consider inapplicable items at the start of the list
            var firstApplicable = -1;
            //optimization 2: do not need to continue with quadratic if there is less than 2 applicable results
            var applicableLeft = 0; 
            for (int i = 0; i < candidates.Count; ++i)
            {
                if (candidates[i].Kind == OperatorAnalysisResultKind.Applicable)
                {
                    if (firstApplicable == -1)
                    {
                        firstApplicable = i;
                    }
                    applicableLeft++;
                }
            }
            if (applicableLeft < 2)
            {
                return;
            }
            for (int i = firstApplicable; i < candidates.Count; ++i)
            {
                if (candidates[i].Kind != OperatorAnalysisResultKind.Applicable)
                {
                    continue;
                }

                // Is this applicable operator better than every other applicable method?
                for (int j = firstApplicable; j < candidates.Count; ++j)
                {
                    if (i == j)
                    {
                        continue;
                    }
                    if (candidates[j].Kind == OperatorAnalysisResultKind.Inapplicable)
                    {
                        continue;
                    }
                    var better = BetterOperator(candidates[i].Signature, candidates[j].Signature, left, right, ref useSiteDiagnostics);
                    if (better == BetterResult.Left && candidates[j].Kind != OperatorAnalysisResultKind.Worse)
                    {
                        candidates[j] = candidates[j].Worse();
                        applicableLeft--;
                    }
                    else if (better == BetterResult.Right && candidates[i].Kind != OperatorAnalysisResultKind.Worse)
                    {
                        candidates[i] = candidates[i].Worse();
                        applicableLeft--;
                    }

                    if (applicableLeft < 2)
                    {
                        //a single "best" candidate is now known...
                        //it is still possible that there exists an operator better than this one that is already known worse than some other one
                        return;
                    }
                }
            }
        }

        public static void GetQuadraticResults(List<Candidate> candidates)
        {
            object useSiteDiagnostics = new object();
            object right = null;
            object left = null;

            for (int i = 0; i < candidates.Count; ++i)
            {
                if (candidates[i].Kind != OperatorAnalysisResultKind.Applicable)
                {
                    continue;
                }

                // Is this applicable operator better than every other applicable method?
                for (int j = 0; j < candidates.Count; ++j)
                {
                    if (i == j)
                    {
                        continue;
                    }
                    if (candidates[j].Kind == OperatorAnalysisResultKind.Inapplicable)
                    {
                        continue;
                    }
                    var better = BetterOperator(candidates[i].Signature, candidates[j].Signature, left, right, ref useSiteDiagnostics);
                    if (better == BetterResult.Left)
                    {
                        candidates[j] = candidates[j].Worse();
                    }
                    else if (better == BetterResult.Right)
                    {
                        candidates[i] = candidates[i].Worse();
                    }
                }
            }
        }

        private static BetterResult BetterOperator(Signature left, Signature right, object o, object o1, ref object o3)
        {
            if (left.IsBetterThan(right)) { return BetterResult.Left; }
            if (right.IsBetterThan(left)) { return BetterResult.Right; }
            return BetterResult.Neither;
        }
    }

    public enum BetterResult { Left, Right, Neither }

    public class Candidate
    {
        public OperatorAnalysisResultKind Kind { get; set; } = OperatorAnalysisResultKind.Applicable;
        public Signature Signature { get; set; }
        public Candidate Worse() { return new Candidate { Signature = Signature, Kind = OperatorAnalysisResultKind.Worse }; }
        public override string ToString() => "{" + Signature + "}";
    }

    public class Signature
    {
        readonly List<Signature> _worse = new List<Signature>();
        public bool IsBetterThan(Signature s) => _worse.Contains(s);
        public void MakeBatterThan(Signature s) => _worse.Add(s);

        public string Name { get; set; }

        public override string ToString() => Name + ": " + string.Join(",", _worse.Select(w => w.Name));
    }

    public enum OperatorAnalysisResultKind
    {
        Applicable,
        Inapplicable,
        Worse
    }
}

project.json

{
  "version": "1.0.0-*",
  "buildOptions": {
    "emitEntryPoint": true
  },
  "runtimes": {
    "win7-x64": {},
    "win10-x64": {}
  },

  "dependencies": {
    "Combinatorics": "1.0.3.2"
  },

  "frameworks": {
    "net461": {}
  }
}