Advertisement
Guest User

Untitled

a guest
Jul 2nd, 2015
367
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Problem 1Add(T) Complexity -> Worst Case :
  2.  
  3.     public void Add(T item) {
  4.         var newArr = new T[this.arr.Length + 1];            // O(1)
  5.         Array.Copy(this.arr, newArr, this.arr.Length);      // O(n)
  6.         newArr[newArr.Length - 1] = item;                   // O(1)
  7.         this.arr = newArr;                                  // O(1)
  8.     }
  9.  
  10.     T(n) = O(n)
  11.  
  12. -------------------------------------------------------------------
  13.  
  14. Problem 2Remove(index) Complexity –> Worst Case :
  15.  
  16.     public T Remove(int index) {
  17.         T result = this.arr[index];                                                         O(1)
  18.         var newArr = new T[this.arr.Length - 1];                                            O(1)
  19.         Array.Copy(this.arr, newArr, index);                                                O(n)
  20.         Array.Copy(this.arr, index + 1, newArr, index, this.arr.Length - index - 1);        O(n)
  21.         this.arr = newArr;                                                                  O(1)
  22.         return result;                                                                      O(1)
  23.     }
  24.  
  25.     T(n) = O(n)
  26.  
  27. -------------------------------------------------------------------
  28.  
  29. Problem 3Remove(index) Complexity –> Best Case :
  30.  
  31.     public T Remove(int index) {
  32.         T result = this.arr[index];                                                         O(1)
  33.         var newArr = new T[this.arr.Length - 1];                                            O(1)
  34.         Array.Copy(this.arr, newArr, index);                                                O(1)
  35.         Array.Copy(this.arr, index + 1, newArr, index, this.arr.Length - index - 1);        O(1)
  36.         this.arr = newArr;                                                                  O(1)
  37.         return result;                                                                      O(1)
  38.     }
  39.  
  40.     T(n) = O(1)
  41.  
  42. -------------------------------------------------------------------
  43.  
  44. Problem 4Remove(index) Complexity – Average Case :
  45.  
  46.     public T Remove(int index) {
  47.         T result = this.arr[index];                                                         O(1)
  48.         var newArr = new T[this.arr.Length - 1];                                            O(1)
  49.         Array.Copy(this.arr, newArr, index);                                                O(1)
  50.         Array.Copy(this.arr, index + 1, newArr, index, this.arr.Length - index - 1);        O(1)
  51.         this.arr = newArr;                                                                  O(1)
  52.         return result;                                                                      O(1)
  53.     }
  54.  
  55.     T(n) = O(1)
  56.  
  57. -------------------------------------------------------------------
  58.  
  59. Problem 5RemoveFirst(T) Complexity :
  60.  
  61.     public T RemoveFirst() {
  62.         return this.Remove(0);      O(1)
  63.     }
  64.  
  65.     T(n) = O(1)
  66.  
  67. -------------------------------------------------------------------
  68.  
  69. Problem 6RemoveLast(T) Complexity :
  70.  
  71.     public T RemoveLast() {
  72.         return this.Remove(this.Length - 1);    O(1)
  73.     }
  74.  
  75.     T(n) = O(1)
  76.  
  77. -------------------------------------------------------------------
  78.  
  79. Problem 7Length Complexity :
  80.  
  81.     public int Length {
  82.         get { return this.arr.Length; }     O(1)
  83.     }
  84.  
  85.     T(n) = O(1)
  86.  
  87. -------------------------------------------------------------------
  88.  
  89. Problem 8This[index] Complexity :
  90.  
  91.     public T this[int index] {
  92.         get { return this.arr[index]; }     O(1)
  93.     }
  94.  
  95.     T(n) = O(1)
  96.  
  97. -------------------------------------------------------------------
  98.  
  99. Problem 9First Complexity :
  100.  
  101.     public T First {
  102.         get { return this.arr[0]; }     O(1)
  103.     }
  104.  
  105.     T(n) = O(1)
  106.  
  107. -------------------------------------------------------------------
  108.  
  109. Problem 10. Last Complexity :
  110.  
  111. public T Last {
  112.     get { return this.arr[this.arr.Length - 1]; }   O(1)
  113. }
  114.  
  115. T(n) = O(1)
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement