DataStructuresAlgorithmsAndComplexityTask1

/*
 * Task 1
 * What is the expected running time of the
 * following C# code? Explain why.
 * Assume the array's size is n.
 */

namespace Task1
{
    using System;
    using System.Diagnostics;

    public class Task1
    {
        /// <summary>
        /// Original Code from homework.
        /// </summary>
        public static long ComputeOriginal(int[] arr)
        {
            long count = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                int start = 0, end = arr.Length - 1;
                while (start < end)
                    if (arr[start] < arr[end])
                    { start++; count++; }
                    else
                        end--;
            }
            return count;
        }

        /*
         * Runing time of this code is: O(n * n)
         * Because for every element in array
         * we check(acess) every element of array - n * n!
         * Major improving is available with time O(n):
         */

        /// <summary>
        /// Major improved code.
        /// </summary>
        public static long ComputeImproved(int[] array)
        {
            int result = 0;
            for (int i = array.Length - 1; i > 0; i--)
            {
                if (array[result] < array[i])
                {
                    result = i;
                }
            }

            result = result * array.Length;
            return result;
        }

        /// <summary>
        /// Test original and improved code.
        /// </summary>
        private static void Main()
        {
            int[] testArray = new int[] { 1, 2, 4, -5, 3, 333, -333 };

            Console.WriteLine(ComputeOriginal(testArray));
            Console.WriteLine(ComputeImproved(testArray));

            // Compare fixed and major improved code
            int repeats = 10000000;
            Stopwatch timer = new Stopwatch();
            timer.Start();
            for (int i = 0; i < repeats; i++)
            {
                ComputeOriginal(testArray);
            }

            timer.Stop();
            Console.WriteLine("Time of original code after {0} repeats: {1}", repeats, timer.Elapsed);

            timer.Reset();

            timer.Start();
            for (int i = 0; i < repeats; i++)
            {
                ComputeImproved(testArray);
            }

            timer.Stop();
            Console.WriteLine("Time of major improved code after {0} repeats: {1}", repeats, timer.Elapsed);
        }
    }
}