Advertisement
Guest User

Algorithm Complexity

a guest
Jul 2nd, 2015
392
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ----------------------------------------------------------
  2. Sample Class - StupidList
  3. ----------------------------------------------------------
  4.  
  5. public class StupidList<T>
  6. {
  7. private T[] arr = new T[0];
  8.  
  9. public int Length
  10. {
  11. get
  12. {
  13. return this.arr.Length;
  14. }
  15. }
  16.  
  17. public T this[int index]
  18. {
  19. get
  20. {
  21. return this.arr[index];
  22. }
  23. }
  24.  
  25. public T First
  26. {
  27. get
  28. {
  29. return this.arr[0];
  30. }
  31. }
  32.  
  33. public T Last
  34. {
  35. get
  36. {
  37. return this.arr[this.arr.Length - 1];
  38. }
  39. }
  40.  
  41. public void Add(T item)
  42. {
  43. var newArr = new T[this.arr.Length + 1];
  44. Array.Copy(this.arr, newArr, this.arr.Length);
  45. newArr[newArr.Length - 1] = item;
  46. this.arr = newArr;
  47. }
  48.  
  49. public T Remove(int index)
  50. {
  51. T result = this.arr[index];
  52. var newArr = new T[this.arr.Length - 1];
  53. Array.Copy(this.arr, newArr, index);
  54. Array.Copy(this.arr, index + 1, newArr, index, this.arr.Length - index - 1);
  55. this.arr = newArr;
  56. return result;
  57. }
  58.  
  59. public T RemoveFirst()
  60. {
  61. return this.Remove(0);
  62. }
  63.  
  64. public T RemoveLast()
  65. {
  66. return this.Remove(this.Length - 1);
  67. }
  68. }
  69.  
  70.  
  71. ----------------------------------------------------------
  72. Problem 1. Add(T) Complexity
  73. ----------------------------------------------------------
  74.  
  75. We ignore the allocation process and all the assignments processes because they are not interesting as to running time and we
  76. could mark them as C (Constant).
  77.  
  78. However, what is interesting is this:
  79. Array.Copy(this.arr, index + 1, newArr, index, this.arr.Length - index - 1);
  80.  
  81. We take every element from the first array and copy it to the other one. That means we have to iterate through the
  82. first array N times where N is the number of elements in it. Therefore we can say that the running time is:
  83. N + C or simply O(N)
  84.  
  85. ----------------------------------------------------------
  86. Problem 2. Remove(index) Complexity – Worst Case
  87. ----------------------------------------------------------
  88.  
  89. Again we ignore the allocation and object creation processes as they are not interesting for calculating the running time.
  90.  
  91. We can see that we take the first half of the array and copy it and after that the other half without the removed index.
  92. That is what we are looking for. And it seems we are iterating through the array N - 1 times since we are iterating all of
  93. the elements without the removed index.
  94.  
  95. Therefore, we could say that the running time is (N - 1) + C or again O(N).
  96.  
  97. ----------------------------------------------------------
  98. Problem 3. Remove(index) Complexity – Best Case
  99. ----------------------------------------------------------
  100.  
  101. In this scenario, the best case is the same as the worst case, since it doesn't matter which index we remove,
  102. the array will still be iterated (N - 1) times. The only scenario in which that is not going to happen is if we
  103. input a wrong index and that would cause an exception.
  104.  
  105. Therefore, I would say that the running time in the best case is still O(N).
  106.  
  107. ----------------------------------------------------------
  108. Problem 4. Remove(index) Complexity – Average Case
  109. ----------------------------------------------------------
  110.  
  111. As stated above, I think that the complexity is still O(N) in all cases.
  112.  
  113. ----------------------------------------------------------
  114. Problem 5. RemoveFirst(T) Complexity
  115. ----------------------------------------------------------
  116.  
  117. This method uses the method Remove(index), therefore it has the same complexity as the method - O(N)
  118.  
  119. ----------------------------------------------------------
  120. Problem 6. RemoveLast(T) Complexity
  121. ----------------------------------------------------------
  122.  
  123. Again, this one uses the same method as stated above, the complexity is still O(N)
  124.  
  125. ----------------------------------------------------------
  126. Problem 7. Length Complexity
  127. ----------------------------------------------------------
  128.  
  129. This method simply returns the array length in constant time with no iteration. Therefore the complexity is O(1) or O(C).
  130.  
  131. ----------------------------------------------------------
  132. Problem 8. This[index] Complexity
  133. ----------------------------------------------------------
  134.  
  135. This method works in a similar way as the previous way. It simply accesses the element without iterating anything.
  136. The complexity is O(1).
  137.  
  138. ----------------------------------------------------------
  139. Problem 9. First Complexity
  140. ----------------------------------------------------------
  141.  
  142. This method accesses an element from the array directly and so, it has a complexity of O(1).
  143.  
  144. ----------------------------------------------------------
  145. Problem 10. Last Complexity
  146. ----------------------------------------------------------
  147.  
  148. This one works in a similar way. The only difference is that it uses the .Length property of the array as well.
  149. Therefore, we could say this one is a bit slower than the previous one, but it isn't enough to make a
  150. significant difference. The complexity is still O(1).
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement