O Notation with C# (CSharp) – My Take

Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm. Big O notation is a measure of the complexity of your program in terms of the size of the input. The size of the input is usually denote as ‘n’. There are usually 2 ways to measure the complexity:

  • Time: The number of calculations your program must perform on the input data to get the ouput. For example finding the biggest number in a list of n numbers requires you to check every number against against your current maximum and see if the new number is higher. Thus for n numbers you need n checks, or calculations. This has linear time complexity because there is a 1 to 1 relationship between input the number of calculations to obtain the output. Linear time complexity is denoted as O(n).
  • Space: The amount of storage space needed by the program to run its calculations. We will the above example of finding the biggest number in a list of n numbers. We need a variable to store our current maximum number value. If we have 10 numbers, we need 1 variable, if we have a million numbers, we still need 1 variable. The number of variables we need is constant compared to the input size, so our program has constant space complexity, denoted as O(1).

O(1)

O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set.

private static bool IsFirstElementNullOrEmpty(List<string> elements)
{
    if (elements == null)
        throw new ArgumentNullException("elements");
 
    if (elements.Count > 0)
    {
        if (string.IsNullOrEmpty(elements[0]))
        {
            return true;
        }
    }
    return false;
}

O(n)

O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. The example below also demonstrates how Big O favours the worst-case performance scenario; a matching string could be found during any iteration of the for loop and the function would return early, but Big O notation will always assume the upper limit where the algorithm will perform the maximum number of iterations.

private static bool ContainsValue(List<string> elements, string elementToBeFound)
{
    if (elements == null)
        throw new ArgumentNullException("elements");
 
    if (elements.Count > 0)
    {
        for (int count = 0; count < elements.Count; count++)
        {
            if (elements[count].Equals(elementToBeFound))
            {
                return true;
            }
        }
    }
    return false;
}

O(N2) (n Square)

O(N2) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. This is common with algorithms that involve nested iterations over the data set. Deeper nested iterations will result in O(N3), O(N4) etc.

private static bool ContainsDuplicate(List<string> elements)
{
    if (elements == null)
        throw new ArgumentNullException("elements");
 
    if (elements.Count > 0)
    {
        for (int count = 0; count < elements.Count; count++)
        {
            for (int innerCount = 0; innerCount < elements.Count; innerCount++)
            {
                if (count == innerCount)
                {
                    continue;
                }
                if (elements[count].Equals(elements[innerCount]))
                {
                    return true;
                }
            }
        }
    }
    return false;
}

Above program can be more efficient to find duplicates like shown below

private static bool ContainsDuplicateEfficient(List<string> elements)
{
    if (elements == null)
        throw new ArgumentNullException("elements");
 
    if (elements.Count > 0)
    {
        for (int count = 0; count < elements.Count; count++)
        {
            for (int innerCount = count; innerCount < elements.Count; innerCount++)
            {
                if (elements[count].Equals(elements[innerCount]))
                {
                    return true;
                }
            }
        }
    }
    return false;
}

Another classic example for same O Notation (O(N2)) is bubble sort
The algorithm works by comparing each item in the list with the item next to it, and swapping them if required. In other words, the largest element has bubbled to the top of the array. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items. The worst-case run time complexity is O(n2).

/// <summary>
/// Bubble Sorting
/// </summary>
/// <param name="scrambledArray">This Parameter Could be array as well, 
/// but for simplicity I have just taken list, I am aware that u can peform binary search on list e.g. numberElements.BinarySearch(55);</param>
/// <returns></returns>
private static int[] BubbleSort(int[] scrambledArray)
{
    for (int count = scrambledArray.Length - 1; count >= 0; count--)
    {
        for (int innercount = 1; innercount <= count; innercount++)
        {
            if (scrambledArray[innercount - 1] > scrambledArray[innercount])
            {
                int temp = scrambledArray[innercount - 1];
                scrambledArray[innercount - 1] = scrambledArray[innercount];
                scrambledArray[innercount] = temp;
            }
        }
    }
    return scrambledArray;
}

The worst-case runtime complexity is O(n2). See explanation below

bubbleSort

O(log n)

An algorithm is said to take logarithmic time if T(n) = O(log n). Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search.An O(log n) algorithm is considered highly efficient, as the operations per instance required to complete decrease with each instance.The most common attributes of logarithmic running-time function are that:

  • the choice of the next element on which to perform some action is one of several possibilities, and
  • only one will need to be chosen.

or

  • the elements on which the action is performed are digits of n

This is why, for example, looking up people in a phone book is O(log n). You don’t need to check every person in the phone book to find the right one; instead, you can simply divide-and-conquer, and you only need to explore a tiny fraction of the entire space before you eventually find someone’s phone number. Of course, a bigger phone book will still take you a longer time, but it won’t grow as quickly as the proportional increase in the additional size.
What does it mean to say that the height of a complete binary tree is O(log n)?. The following drawing depicts a binary tree. Notice how each level contains the double number of nodes compared to the level above (hence binary):
BinaryTree

Binary search is an example with complexity O(log n). Let’s say that the nodes in the bottom level of the tree in figure 1 represents items in some sorted collection. Binary search is a divide-and-conquer algorithm, and the drawing shows how we will need (at most) 4 comparisons to find the record we are searching for in this 16 item dataset.

Assume we had instead a dataset with 32 elements. Continue the drawing above to find that we will now need 5 comparisons to find what we are search for, as the tree has only grown one level deeper when we multiplied the amount of data. As a result, the complexity of the algorithm can be described as a logarithmic order.

Plotting log(n) on a plain piece of paper, will result in a graph where the rise of the curve decelerates as n increases:

BinaryTreeGraph
Algorithms based on binary trees are often O(logn). This is because a perfectly balanced binary search tree has logn layers, and to search for any element in a binary search tree requires traversing a single node on each layer.

The binary search algorithm is another example of a O(log n) algorithm. In a binary search, one is searching through an ordered array and, beginning in the middle of the remaining space to be searched, whether to search the top or the bottom half. You can divide the array in half only logn times before you reach a single element, which is the element being searched for, assuming it is in the array.

BinarySearch optimizes searches on sorted collections. We evaluate the BinarySearch method on List and arrays. We may have a variable number of elements. Binary search is an amazing algorithm that hones in on values in sorted collections. Complexity: Binary search has O(log n) complexity, making it more efficient than others.

Binary search is one of the most basic yet very useful algorithms. It can operate on sorted arrays or range of values. Some people consider it divide and conquer algorithm, others don`t, but it does not really matter. The goal of binary search is to find a specified value (or its index) within an array or a range of values, it can also be used to search for a unknown value which must meet certain known conditions. It defines start, end and middle points for the sorted array or range in which it will be performing a search. On each iteration, depending on how the value at the middle point compares to the value we are searching for, it redefines the start or end point and subsequently the middle point. This way the size of the array or range we are searching in is effectively halved every iteration until we find what we search for or the exit conditions are met before that (we have found nothing). The exit condition is start point > end point.

/// <summary>
 /// Find ValuePosition Using Binary Search
 /// Binary Search can be performed on sorter elements.
 /// Assumption : No Duplicate Elements.
 /// </summary>
 /// <param name="numberElements">This Parameter Could be array as well, 
 /// but for simplicity I have just taken list, I am aware that u can peform binary search on list e.g. numberElements.BinarySearch(55);</param>
 /// <param name="valuesToBeSearched"></param>
 /// <returns></returns>
 private static int FindValuePositionUsingBinarySearch(List<int> numberElements, int valuesToBeSearched)
 {
     if (numberElements == null)
         throw new ArgumentNullException("numberElements");
 
     if (numberElements[0] > valuesToBeSearched)
         return -1;
 
     if (valuesToBeSearched > numberElements[numberElements.Count - 1])
         return -1;
 
     int upperBound = numberElements.Count;
     int lowerBound = 0;
 
     while (lowerBound < upperBound)
     {
         int mid = (upperBound + lowerBound) / 2;
         if (numberElements[mid] < valuesToBeSearched)
         {
             lowerBound = mid;
         }
         else if (numberElements[mid] > valuesToBeSearched)
         {
             upperBound = mid;
         }
         else
         {
             return mid;
         }
     }
     return -1;
 }

O (n log n)

Often, good sorting algorithms are roughly O(nlogn). An example of an algorithm with this efficiency is merge sort, which breaks up an array into two halves, sorts those two halves by recursively calling itself on them, and then merging the result back into a single array. Because it splits the array in half each time, the outer loop has an efficiency of logn, and for each “level” of the array that has been split up (when the array is in two halves, then in quarters, and so forth), it will have to merge together all of the elements, an operations that has order of n.
Complexity can b explained below
mergesort_complexity

/// <summary>
/// Merge Sort
/// </summary>
/// <param name="inputItems">Array to be Sorted</param>
/// <param name="lowerBound">Lower Bound</param>
/// <param name="upperBound">Upper Bound</param>
/// <returns>Sorted Array</returns>
public static int[] MergeSort(int[] inputItems, int lowerBound, int upperBound)
{
    if (lowerBound < upperBound)
    {
        int middle = (lowerBound + upperBound) / 2;
 
        MergeSort(inputItems, lowerBound, middle);
        MergeSort(inputItems, middle + 1, upperBound);
 
        //Merge
        int[] leftArray = new int[middle - lowerBound + 1];
        int[] rightArray = new int[upperBound - middle];
 
        Array.Copy(inputItems, lowerBound, leftArray, 0, middle - lowerBound + 1);
        Array.Copy(inputItems, middle + 1, rightArray, 0, upperBound - middle);
 
        int i = 0;
        int j = 0;
        for (int count = lowerBound; count < upperBound + 1; count++)
        {
            if (i == leftArray.Length)
            {
                inputItems[count] = rightArray[j];
                j++;
            }
            else if (j == rightArray.Length)
            {
                inputItems[count] = leftArray[i];
                i++;
            }
            else if (leftArray[i] <= rightArray[j])
            {
                inputItems[count] = leftArray[i];
                i++;
            }
            else
            {
                inputItems[count] = rightArray[j];
                j++;
            }
        }
    }
    return inputItems;
}

Attached is the Source Code Over Here

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