SHARE
TWEET

DataStructuresAlgorithmsAndComplexityTask1

g-stoyanov May 30th, 2013 121 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * Task 1
  3.  * What is the expected running time of the
  4.  * following C# code? Explain why.
  5.  * Assume the array's size is n.
  6.  */
  7.  
  8. namespace Task1
  9. {
  10.     using System;
  11.     using System.Diagnostics;
  12.  
  13.     public class Task1
  14.     {
  15.         /// <summary>
  16.         /// Original Code from homework.
  17.         /// </summary>
  18.         public static long ComputeOriginal(int[] arr)
  19.         {
  20.             long count = 0;
  21.             for (int i = 0; i < arr.Length; i++)
  22.             {
  23.                 int start = 0, end = arr.Length - 1;
  24.                 while (start < end)
  25.                     if (arr[start] < arr[end])
  26.                     { start++; count++; }
  27.                     else
  28.                         end--;
  29.             }
  30.             return count;
  31.         }
  32.  
  33.         /*
  34.          * Runing time of this code is: O(n * n)
  35.          * Because for every element in array
  36.          * we check(acess) every element of array - n * n!
  37.          * Major improving is available with time O(n):
  38.          */
  39.  
  40.         /// <summary>
  41.         /// Major improved code.
  42.         /// </summary>
  43.         public static long ComputeImproved(int[] array)
  44.         {
  45.             int result = 0;
  46.             for (int i = array.Length - 1; i > 0; i--)
  47.             {
  48.                 if (array[result] < array[i])
  49.                 {
  50.                     result = i;
  51.                 }
  52.             }
  53.  
  54.             result = result * array.Length;
  55.             return result;
  56.         }
  57.  
  58.         /// <summary>
  59.         /// Test original and improved code.
  60.         /// </summary>
  61.         private static void Main()
  62.         {
  63.             int[] testArray = new int[] { 1, 2, 4, -5, 3, 333, -333 };
  64.            
  65.             Console.WriteLine(ComputeOriginal(testArray));
  66.             Console.WriteLine(ComputeImproved(testArray));
  67.  
  68.             // Compare fixed and major improved code
  69.             int repeats = 10000000;
  70.             Stopwatch timer = new Stopwatch();
  71.             timer.Start();
  72.             for (int i = 0; i < repeats; i++)
  73.             {
  74.                 ComputeOriginal(testArray);
  75.             }
  76.  
  77.             timer.Stop();
  78.             Console.WriteLine("Time of original code after {0} repeats: {1}", repeats, timer.Elapsed);
  79.  
  80.             timer.Reset();
  81.  
  82.             timer.Start();
  83.             for (int i = 0; i < repeats; i++)
  84.             {
  85.                 ComputeImproved(testArray);
  86.             }
  87.  
  88.             timer.Stop();
  89.             Console.WriteLine("Time of major improved code after {0} repeats: {1}", repeats, timer.Elapsed);    
  90.         }
  91.     }
  92. }
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