DataStructuresAlgorithmsAndComplexityTask3

/*
 * Task 3
 * * What is the expected running time of the
 * following C# code? Explain why.
 * Assume the input matrix has size of n * m.
 */

namespace Task3
{
    using System;
    using System.Diagnostics;

    public class Task3
    {
        /// <summary>
        /// Original Code from homework.
        /// </summary>
        public static long CalcSumOriginal(int[,] matrix, int row)
        {
            long sum = 0;

            // There is a bug in matrix.GetLength(0) - must be matrix.GetLength(1) because this is a number of cols
            for (int col = 0; col < matrix.GetLength(0); col++)
                sum += matrix[row, col];

            // There is a bug in matrix.GetLength(1) - must be matrix.GetLength(0) because this is a number of rows
            if (row + 1 < matrix.GetLength(1))
                sum += CalcSumOriginal(matrix, row + 1);
            return sum;
        }

        /// <summary>
        /// Fixed Code.
        /// </summary>
        public static long CalcSumFixed(int[,] matrix, int row)
        {
            long sum = 0;

            // Bug Fixed
            for (int col = 0; col < matrix.GetLength(1); col++)
            {
                sum = sum + matrix[row, col];
            }

            // Bug Fixed
            if (row + 1 < matrix.GetLength(0))
            {
                sum = sum + CalcSumFixed(matrix, row + 1);
            }

            return sum;
        }

        /*
         * Runing time of this code is: O(n * m)
         * Because for every column we recursive call
         * function for each row in the column - n * m!
         * Minor improving is available:
         */

        /// <summary>
        /// Minor improved code.
        /// </summary>
        public static long CalcSumImproved(int[,] matrix)
        {
            long sum = 0;
            for (int row = 0; row < matrix.GetLength(0); row++)
            {
                for (int col = 0; col < matrix.GetLength(1); col++)
                {
                    sum = sum + matrix[row, col];
                }
            }

            return sum;
        }

        /// <summary>
        /// Test fixed and improved code.
        /// </summary>
        private static void Main()
        {
            // Test fixed code
            int[,] matrix = new int[,]
            {
                { 1, 2, 4, -5, 3 },
                { 122, 33, -56, 22, 3 },
                { 1, 2, 4, -5, 3 },
                { 122, 33, -56, 22, 3 },
            };

            Console.WriteLine(CalcSumFixed(matrix, 0));
            Console.WriteLine(CalcSumImproved(matrix));

            // Compare fixed and minor improved code
            int repeats = 10000000;
            Stopwatch timer = new Stopwatch();
            timer.Start();
            for (int i = 0; i < repeats; i++)
            {
                CalcSumFixed(matrix, 0);
            }

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

            timer.Reset();

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

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