# 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).