BigO Examples

BinarySearch.cs

using System;
using System.Linq;

namespace CsharpCodeExamples
{
    class Program
    {

        static void Main(string[] args)
        {
            // binary search (or binary chop) o(log n) is a Logarithmic algorithum.   
            // Doubling the data only means it needs to do one extra chop.

            int[] data = Enumerable
                .Range(0, 120).ToArray();

            int find = 11;
            int length = data.Length;
            Console.WriteLine(string.Format("Array contains '{0}' items.", data.Length - 1));

            int low = 0;
            int high = data.Length - 1;
            var checkCnt = 0;
            while (low <= high)
            {
                checkCnt++;
                var mid = (low + high) / 2;
                if (find == data[mid])
                {
                    Console.WriteLine(string.Format("{0} can be found at number '{1}'", find, mid));
                    break;
                }
                else if (find < data[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            Console.WriteLine(string.Format("I preformed '{0}' checks", checkCnt));
            Console.ReadLine();

        }
    }
}

LinearComplexity.cs

using System;
using System.Linq;

namespace CsharpCodeExamples
{
    class Program
    {        
        static void Main(string[] args)
        {
            int maxNumberOfItems = 60000000;
            int Min = 0;
            int Max = 2 * maxNumberOfItems;
            Random randNum = new Random();
            int[] data = Enumerable
                .Repeat(0, maxNumberOfItems)
                .Select(i => randNum.Next(Min, Max))
                .ToArray();

            Console.WriteLine(string.Format("Array contains '{0}' items.",data.Length-1));

            var lastItem = data[data.Length-1];
            var checkCnt = 0;
            var startTimer = DateTime.UtcNow;

            // Linear Complexity o(n) means that we must check each item one at a time.  In order to find the item we are looking for.
            // With Linear time the more items you have the more items that must be checked and the slower things will go.            
            for (int i = 0; i < data.Length; i++)
            {
                checkCnt++;
                if (data[i] == lastItem)
                {
                    Console.WriteLine(string.Format("Found '{0}' at position '{1}'", lastItem, i));
                    Console.WriteLine(string.Format("I preformed '{0}' checks", checkCnt));
                    break;
                }
            }
            var stopTimer = DateTime.UtcNow;
            var executionTime = stopTimer.Subtract(startTimer);
            Console.WriteLine(string.Format("Execution time '{0}' minutes '{1}' seconds '{2}' Milliseconds", executionTime.Minutes, executionTime.Seconds, executionTime.Milliseconds));
            Console.ReadLine();

        }
    }
}

QuadraticComplexity.cs

using System;
using System.Linq;

namespace CsharpCodeExamples
{
    class Program
    {
        static void Main(string[] args)
        {
            // Quadratic Complexity the more data you have the more checks it has to make and the more time it will take to run. 
            // if the data is already sorted then the complexity will be liniar o(n) becouse the loop only has to run once.
            // If the data is in the complete wrong order then it will be quadratic o(n2)

            Console.WriteLine("Enter length of array. (int)");

            int maxNumberOfItems = 10;

            var holdPrompt = Console.ReadLine();
            var result = int.TryParse(holdPrompt, out maxNumberOfItems);
            if (!result)
            {
                Console.WriteLine("Must be a number. Hit any key to exit.");
                Console.ReadLine();
                return;
            }

            int Min = 0;
            int Max = 2 * maxNumberOfItems;
            Random randNum = new Random();
            int[] data = Enumerable
                .Repeat(0, maxNumberOfItems)
                .Select(i => randNum.Next(Min, Max))
                .ToArray();

            var checkCnt = 0;
            Console.WriteLine(string.Format("Array contains '{0}' items.", data.Length - 1));
            var startTimer = DateTime.UtcNow;
            for (int n = 1; n < data.Length; n++)
            {
                for (int i = 0; i < data.Length - n; i++)
                {
                    checkCnt++;
                    if (data[i] > data[i + 1])
                    {
                        var hold = data[i];
                        data[i] = data[i + 1];
                        data[i + 1] = hold;
                    }
                }
            }
            var stopTimer = DateTime.UtcNow;
            Console.WriteLine(string.Format("I preformed '{0}' checks", checkCnt));
            var executionTime = stopTimer.Subtract(startTimer);
            Console.WriteLine(string.Format("Execution time '{0}' minutes '{1}' seconds '{2}' Milliseconds", executionTime.Minutes, executionTime.Seconds, executionTime.Milliseconds));
            Console.ReadLine();

        }
    }
}

SimpleStack.cs

using System;

namespace CsharpCodeExamples
{
    class Program
    {
        public class SimpleStack<T>
        {
            int top;
            private T[] data;

            public SimpleStack(int bufferLength)
            {
                data = new T[bufferLength];
            }

            public void Push(T value)
            {
                if (top == data.Length - 1) throw new StackOverflowException();

                // Stacks are constant time becouse we always directly accessing "top nr" item in the data array.  
                // We dont have to look at any other item in the array we know exactly which number item we want
                data[top++] = value;   
            }

            public T Pop()
            {
                if (top == 0)
                    return default(T);

                // Stacks are constant time becouse we always directly accessing "top nr" item in the data array.  
                // We dont have to look at any other item in the array we know exactly which number item we want
                return data[--top];
            }
        }

        static void Main(string[] args)
        {
            // Stacks are known as First in last out data structures.
            
            // Consider a stack of plates on a shelf.  
            // After you wash and dry your dishes you place (pop) each plate onto the stack.
            // When it is time to eat again you take the plate on the top of the stack (pop) to use first.

            // Pushing and poping plates on and off the stack are constant time operations.  It doesnt matter 
            // how many plates are on the stack it will always take the same amount of time to push or 
            // pop a new plate on or off of the stack

            //Initialze the stack with a max of 5 items on it.
            var mystack = new SimpleStack<int?>(5);
            mystack.Push(1);
            mystack.Push(2);
            mystack.Push(3);
            Console.WriteLine("Poped: " + mystack.Pop());   // should be three
            Console.WriteLine("Poped: " + mystack.Pop());   // Should be two
            Console.WriteLine("Poped: " + mystack.Pop());   // should be one
            Console.WriteLine("Poped: " + mystack.Pop());   // Null as there are no more items on the stack
            Console.ReadLine();
        }
    }
}
}