SHARE
TWEET

DataStructuresAlgorithmsAndComplexityTask2

g-stoyanov May 30th, 2013 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * Task 2
  3.  * What is the expected running time of the
  4.  * following C# code? Explain why.
  5.  * Assume the input matrix has size of n * m.
  6.  */
  7.  
  8. namespace Task2
  9. {
  10.     using System;
  11.  
  12.     public class Task2
  13.     {
  14.         /// <summary>
  15.         /// Original Code from homework.
  16.         /// </summary>
  17.         public static long CalcCountOriginal(int[,] matrix)
  18.         {
  19.             long count = 0;
  20.             for (int row = 0; row < matrix.GetLength(0); row++)
  21.                 if (matrix[row, 0] % 2 == 0)
  22.                     for (int col = 0; col < matrix.GetLength(1); col++)
  23.                         if (matrix[row, col] > 0)
  24.                             count++;
  25.             return count;
  26.         }
  27.  
  28.         /// <summary>
  29.         /// Test code.
  30.         /// </summary>
  31.         private static void Main()
  32.         {
  33.             int[,] matrix = new int[,]
  34.             {
  35.                 { 1, 2, 4, -5, 3 },
  36.                 { 122, 33, -56, 22, 3 },
  37.                 { 1, 2, 4, -5, 3 },
  38.                 { 122, 33, -56, 22, 3 },
  39.             };
  40.  
  41.             Console.WriteLine(CalcCountOriginal(matrix));
  42.         }
  43.  
  44.         /*
  45.          * Runing time of this code is: O(n * m)
  46.          * Because for every row with first element wich is even  
  47.          * we check all columns of row --- odd <-> even is fifty <-> fifty ;)
  48.          * and therefore formula is n/2 * m ---> O(n * m).
  49.          * No improving is available - this is optimal code!
  50.          */
  51.     }
  52. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top