Find the numbers larger than them in the collection and determine which algorithm is better by comparing their algorithmic complexity

Introduction

Algorithmic complexity plays an extremely important point when scaling an application. Complexity analysis helps us to understand and improve the efficiency of our code. This question though does not have any real time significance but will help us to determine which algorithm is better by comparing their algorithmic complexity.

Let's say we have a collection of numbers like { 20,67,23,39,9,56,43,53,52 }. Now the objective is to find those numbers which are greater than the rest in the collection while compare with their right elements. Indicates that 20 compared to 39 is less and cannot be consider. While 67 compared to 220,67,23,39,9,56,43,53 and 52 is always greater and hence will be consider. Likewise 23, 39, 9 will be discarded. But 56 compared to 43,53,52 is greater. So for 53. And since 52 is the rightmost element will always be consider. So in the final result will be 67,56,53,52

Solution 1

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

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {

            var intCollection = new List<int>() { 20, 67, 23, 39, 9, 56, 43, 53, 52 };
            var discardedElements = new List<int>();

             for(int i=0;i< intCollection.Count;i++)
             {
                 for(int j=i+1;j< intCollection.Count; j++)
                 {
                     if (intCollection[i] < intCollection[j])
                     {
                         discardedElements.Add(intCollection[i]);
                     }
                 }
             }
             Console.WriteLine("Successful elements are");
             intCollection.Except(discardedElements).ToList().ForEach(i => Console.WriteLine("{0}", i));
             Console.ReadKey();
        } 
    }
}

/* 

Successful elements are
67
56
53
52

*/

Here we are performing two looping . The outer loop goes by element by element starting from the first element. The inner loop, goes from the second element in teh series and then we compare the first element with all other elements in the collection. If we find that the element we started with is less than with any other following element in the series then we included that in the discardedElements set. The operation continutes in this way until everything is exhausted in the given collection. Then we find out the elements that are not in the original collection by performing an Except between intCollection and discardedElements and finally print the result. Here the algorithmic complexity is O(N*M) since for every outer element(N), the inner loop executes M=N-1 times.

Solution 2

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

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        { 
           
            var intCollection = new List<Int32>() { 20, 67, 23, 39, 9, 56, 43, 53, 52 };
            var intResults = new List<Int32>();
            var currentMaxValue = Int32.MinValue;

            for (Int32 i = intCollection.Count - 1; i >= 0; --i)
            {
                if (intCollection[i] > currentMaxValue)
                {
                    currentMaxValue = intCollection[i];
                    intResults.Insert(0, intCollection[i]);
                }
            }

            Console.WriteLine("Successful elements are");
            intResults.ForEach(i => Console.WriteLine("{0}", i));
            Console.ReadKey();
        }       
    }
}

/* 

Successful elements are
67
56
53
52

*/

Here we are taking a different approach. We are reading teh elements from right to left. Now consider the first element which is 52. It has satisfied the condition intCollection[i] > currentMaxValue and hence is included in the intResults list and also the currentMaxValue is set to 52. Next time, for teh second element in teh series, 53 has also satistifes the condition and so the currentMaxValue is set to 53 which 53 has found it's place in the intResults list. The third element is 43. It could not pass the condition intCollection[i] > currentMaxValue and is hence discarded. In this way the program goes on. Here the algorithmic complexity is O(N) since we have only one loop to execute. A little overhead is there the conditional check but that can be treated as a constant and is negligible.

On the basis of the above analysis, it can be infer that, the second algorithm is better as compared to the first one and is the winner between these two.

Reference

Conclusion

In this article we have learnt the use and benefit of algorithmic complexity in determining a solution for a problem . Hope this will be useful. Thanks for reading.