Algorithmic Efficiency

Algorithmic efficiency are the properties of an algorithm which relate to the amount of resources used by the algorithm. An algorithm must be analysed to determine its resource usage.

While writing code and selecting the data structure always check for the Big O notation.

There are many Big O(order) notation but below there are the most commonly used notations

Order 1 or O(1) complexity also known as Constant Time: In this time will remain constant to complete the operation even if overhead increased.

Example: Let’s assume that we need to find out whether the last element in the array is even no. or not.

As we all know that extracting the element from specific position of an array is faster so below code will always return the output faster even if overhead increased.

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

namespace Algorithmic
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(isLastNumberEven(new int[]{1,2,35,6,7,8}));
            Console.ReadKey();
        }

        public static bool isLastNumberEven(int[] Arr){
            int LastIndex = Arr.Length;
            if (Arr[LastIndex-1] % 2 == 0) {
                return true;
            }
                return false;
        }
    }
}

O(n) complexity – linear time: It means time is depend on the overhead, if code is taking 5 seconds to process lets say 100 records then it will take 10 seconds to process 200 records.

Console.WriteLine(CountEvenNumbers(new int[] { 1, 2, 35, 6, 7, 8, 9 }));

public static int CountEvenNumbers(int[] Arr) {
        int Counter = 0;

        for (int i = 0; i < Arr.Length; i++) {
            if (Arr[i] % 2 == 0) {
                    Counter++;
            }
         }
            
         return Counter;
}

O(n2) complexity – quadratic time: This happens when we have the nested iterations in the program on the same collection. Below is the example for this.

 Console.WriteLine(FindDuplicates(new int[] { 1, 2, 35, 6, 7, 8, 9,2 }));
 public static bool FindDuplicates(int[] Arr)
 { 
            
    for(int i = 0; i < Arr.Length; i++){
          for(int j = i+1; j < Arr.Length; j++){
               if (Arr[i] == Arr[j]) {
                  return true;
               }
          }
    }
    return false;

 }

So, what to look for in code?

1) Nested iterations
2) Instantiation inside the iterations (this is basically for memory management).
3) Selection of correct data structure for collections.
example:
Array Operations
//direct indexing : O(1)
//searching: O(n)
//sorting: O(n log n)
4) Immutable are generally faster – less overhead.
5) Consider converting mutable to immutable once loaded.
6) Collection questions:
>> Do we need to search (find object in) the collection?
>> Need to order (sort) it? Should it always be sorted?
>> Do we need to enumerate the entire collection?
>> Does it change size?
>> Do we need to pull / push items in / out?
7) Use stringbuilder / stringbuffer / mutablestring instead of string to perform string operation.

Summary:
>> Always profile.
>> Concentrate effort on iterated code.
>> Think about what the statement needs to do.
>> Research the collection types of your language.
>> Beware large string operations.
>> Realize some things just take time.

Complete code

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

namespace Algorithmic
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(isLastNumberEven(new int[]{1,2,35,6,7,8,9}));
            Console.WriteLine(CountEvenNumbers(new int[] { 1, 2, 35, 6, 7, 8, 9 }));
            Console.WriteLine(FindDuplicates(new int[] { 1, 2, 35, 6, 7, 8, 9,2 }));
            Console.ReadKey();
        }

        public static bool isLastNumberEven(int[] Arr){
            int LastIndex = Arr.Length;
            if (Arr[LastIndex-1] % 2 == 0) {
                return true;
            }
                return false;
        }

        public static int CountEvenNumbers(int[] Arr) {
            int Counter = 0;

            for (int i = 0; i < Arr.Length; i++) {
                if (Arr[i] % 2 == 0) {
                    Counter++;
                }
            }
            
            return Counter;
        }


        public static bool FindDuplicates(int[] Arr)
        { 
            
            for(int i = 0; i < Arr.Length; i++){
                for(int j = i+1; j < Arr.Length; j++){
                    if (Arr[i] == Arr[j]) {
                        return true;
                    }
                }
            }
            return false;

        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s