API tools faq
paste
Advertisement
ChazPIerre

O

ChazPIerre
Jan 18th, 2021
2,556
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 16.30 KB | None | 0 0
raw download clone embed print report
  1. # Part A - A2 Analysis
  2.  
  3. ### numRecords()
  4. Let NR(n) represent the number of operations needed
  5. ```cpp
  6. template <class TYPE>
  7. int SimpleTable<TYPE>::numRecords() const{
  8.     int rc=0; // 1
  9.     for(int i=0;records_[i]!=nullptr;i++){ // 1 + n + n
  10.         rc++; // n
  11.     }
  12.     return rc; // 1
  13. }
  14. ```
  15. NR(n) = 1 + 1 + n + n + n + 1  
  16. NR(n) = 3n + 3  
  17. NR(n) is O(n)  
  18.  
  19. ### update() - if item does not exists so you need to add it as a new record, assume no grow() call is made
  20. Let U(n) represent the number of operations needed
  21. ```cpp
  22. template <class TYPE>
  23. void SimpleTable<TYPE>::update(const std::string& key, const TYPE& value){
  24.     int idx=-1; // 1
  25.     int size=numRecords(); // 1 + NR(n)
  26.     for(int i=0;i<size;i++){ // 1 + n + n
  27.         if(records_[i]->key_ == key){ // n + n
  28.                   idx=i;
  29.         }
  30.     }
  31.     if(idx==-1){ // 1
  32.         if(size == capacity_){ // 1
  33.             grow();
  34.         }
  35.         records_[size++]=new Record(key,value); // 1 + 1 + 1 + 2 (Record())
  36.         for(int i=size-1;i>0 && records_[i]->key_ < records_[i-1]->key_;i--){ // 2 + 8(n-1) + (n-1)
  37.             Record* tmp=records_[i]; // 2(n-1)
  38.             records_[i]=records_[i-1]; // 4(n-1)
  39.             records_[i-1]=tmp; // 3(n-1)
  40.         }
  41.     }
  42.     else{
  43.         records_[idx]->data_=value;
  44.     }
  45.  
  46. }
  47. ```
  48. U(n) = 1 + 1 + NR(n) + 1 + n + n + n + n + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 8(n-1) + (n-1) + 2(n-1) + 4(n-1) + 3(n-1)  
  49. U(n) = 1 + 1 + 3n + 3 + 1 + n + n + n + n + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 8(n-1) + (n-1) + 2(n-1) + 4(n-1) + 3(n-1)  
  50. U(n) = 7n + 18(n-1) + 15  
  51. U(n) = 7n + 18n + 15 - 18  
  52. U(n) = 25n - 3  
  53. U(n) is O(n)  
  54.  
  55. ### update() - if item does exists and you are just modifying what is there
  56. Let UE(n) represent the number of operations needed
  57. ```cpp
  58. template <class TYPE>
  59. void SimpleTable<TYPE>::update(const std::string& key, const TYPE& value){
  60.     int idx=-1; // 1
  61.     int size=numRecords(); // 1 + NR(n)
  62.     for(int i=0;i<size;i++){ // 1 + n + n
  63.         if(records_[i]->key_ == key){ // n + n
  64.             idx=i;
  65.         }
  66.     }
  67.     if(idx==-1){ // 1
  68.         if(size == capacity_){
  69.             grow();
  70.         }
  71.         records_[size++]=new Record(key,value);
  72.         for(int i=size-1;i>0 && records_[i]->key_ < records_[i-1]->key_;i--){
  73.             Record* tmp=records_[i];
  74.             records_[i]=records_[i-1];
  75.             records_[i-1]=tmp;
  76.         }
  77.     }
  78.     else{
  79.         records_[idx]->data_=value; // 1 + 1 + 1
  80.     }
  81.  
  82. }
  83. ```
  84. UE(n) = 1 + 1 + NR(n) + 1 + n + n + n + n + 1 + 1 + 1 + 1  
  85. UE(n) = 1 + 1 + 3n + 3 + 1 + n + n + n + n + 1 + 1 + 1 + 1  
  86. UE(n) = 7n + 7  
  87. UE(n) is O(n)  
  88.  
  89. ### find() - if item is there
  90. Let F(n) represent the number of operations needed
  91. ```cpp
  92. template <class TYPE>
  93. bool SimpleTable<TYPE>::find(const std::string& key, TYPE& value){
  94.     int idx=-1; // 1
  95.     for(int i=0;i<numRecords();i++){ // 1 + n + n(NR(n)) + n
  96.         if(records_[i]->key_ == key){ // n + n + n
  97.             idx=i; // 1
  98.         }
  99.     }
  100.     if(idx==-1) // 1
  101.         return false;
  102.     else{
  103.         value=records_[idx]->data_; // 1 + 1 + 1
  104.         return true; // 1
  105.     }
  106. }
  107. ```
  108. F(n) = 1 + 1 + n + n(NR(n)) + n + n + n + n + 1 + 1 + 1 + 1 + 1 + 1  
  109. F(n) = 1 + 1 + n + n(3n + 3) + n + n + n + n + 1 + 1 + 1 + 1 + 1 + 1  
  110. F(n) = 5n + n(3n + 3) + 8  
  111. F(n) = 5n + 3n^2 + 3n + 8  
  112. F(n) = 3n^2 + 8n + 8  
  113. F(n) is O(n^2)  
  114.  
  115. ### find() - if item is not there
  116. Let FN(n) represent the number of operations needed
  117. ```cpp
  118. template <class TYPE>
  119. bool SimpleTable<TYPE>::find(const std::string& key, TYPE& value){
  120.     int idx=-1; // 1
  121.     for(int i=0;i<numRecords();i++){ // 1 + n + n(NR(n)) + n
  122.         if(records_[i]->key_ == key){ // n + n + n
  123.             idx=i; // 1
  124.         }
  125.     }
  126.     if(idx==-1) // 1
  127.         return false; // 1
  128.     else{
  129.         value=records_[idx]->data_;
  130.         return true;
  131.     }
  132. }
  133. ```
  134. FN(n) = 1 + 1 + n + n(NR(n)) + n + n + n + n + 1 + 1 + 1  
  135. FN(n) = 1 + 1 + n + n(3n + 3) + n + n + n + n + 1 + 1 + 1  
  136. FN(n) = 5n + n(3n + 3) + 5  
  137. FN(n) = 5n + 3n^2 + 3n + 5  
  138. FN(n) = 3n^2 + 8n + 5  
  139. FN(n) is O(n^2)  
  140.  
  141. ### remove() - if item is there
  142. Let R(n) represent the number of operations needed
  143. ```cpp
  144. template <class TYPE>
  145. bool SimpleTable<TYPE>::remove(const std::string& key){
  146.     int idx=-1; // 1
  147.     for(int i=0;i<numRecords();i++){ // 1 + n + n(NR(n)) + n
  148.         if(records_[i]->key_ == key){ // n + n + n
  149.             idx=i; // 1
  150.         }
  151.     }
  152.     if(idx!=-1){ // 1
  153.         int size=numRecords();  // 1 + NR(n)
  154.         delete records_[idx]; // 1 + 1
  155.         for(int i=idx;i<size-1;i++){ // 1 + (n-1) + (n-1)
  156.             records_[i]=records_[i+1]; // 4(n-1)
  157.         }
  158.         records_[size-1]=nullptr; // 1 + 1 + 1
  159.         return true; // 1
  160.     }
  161.     else{
  162.         return false;
  163.     }
  164. }
  165. ```
  166. R(n) = 1 + 1 + n + n(NR(n)) + n + n + n + n + 1 + 1 + 1 + NR(n) + 1 + 1 + 1 + (n-1) + (n-1) + 4(n-1) + 1 + 1 + 1 + 1  
  167. R(n) = 1 + 1 + n + n(3n + 3) + n + n + n + n + 1 + 1 + 1 + 3n + 3 + 1 + 1 + 1 + (n-1) + (n-1) + 4(n-1) + 1 + 1 + 1 + 1  
  168. R(n) = 8n + 6(n-1) + 12 + n(3n + 3)  
  169. R(n) = 8n + 6(n-1) + 12 + 3n^2 + 3n  
  170. R(n) = 8n + 6n + 12 + 3n^2 + 3n - 6  
  171. R(n) = 3n^2 + 17n + 6  
  172. R(n) is O(n^2)  
  173.  
  174. ### remove() - if item is not there
  175. Let RN(n) represent the number of operations needed
  176. ```cpp
  177. template <class TYPE>
  178. bool SimpleTable<TYPE>::remove(const std::string& key){
  179.     int idx=-1; // 1
  180.     for(int i=0;i<numRecords();i++){ // 1 + n + n(NR(n)) + n
  181.         if(records_[i]->key_ == key){ // n + n + n
  182.             idx=i; // 1
  183.         }
  184.     }
  185.     if(idx!=-1){ // 1
  186.         int size=numRecords();
  187.         delete records_[idx];
  188.         for(int i=idx;i<size-1;i++){
  189.             records_[i]=records_[i+1];
  190.         }
  191.         records_[size-1]=nullptr;
  192.         return true;
  193.     }
  194.     else{
  195.         return false; // 1
  196.     }
  197. }
  198. ```
  199. RN(n) = 1 + 1 + n + n(NR(n)) + n + n + n + n + 1 + 1 + 1  
  200. RN(n) = 1 + 1 + n + n(3n + 3) + n + n + n + n + 1 + 1 + 1  
  201. RN(n) = n(3n + 3) + 5n + 5  
  202. RN(n) = 3n^2 + 3n + 5n + 5  
  203. RN(n) = 3n^2 + 8n + 5  
  204. RN(n) is O(n^2)  
  205.  
  206. ### copy constructor
  207. Let CC(n) represent the number of operations needed
  208. ```cpp
  209. template <class TYPE>
  210. SimpleTable<TYPE>::SimpleTable(const SimpleTable<TYPE>& rhs){
  211.     records_=new Record*[rhs.capacity_]; // 1 + 1 + 1
  212.     capacity_=rhs.capacity_; // 1
  213.     for(int i=0;i<rhs.numRecords();i++){ // 1 + n + n(NR(n)) + n
  214.         update(rhs.records_[i]->key_,rhs.records_[i]->data_); // n(U(n)) + n + n + n + n
  215.     }
  216. }
  217. ```
  218.  
  219. CC(n) = 1 + 1 + 1 + 1 + 1 + n + n(NR(n)) + n + n(U(n)) + n + n + n + n  
  220. CC(n) = 1 + 1 + 1 + 1 + 1 + n + n(3n + 3) + n + n(25n - 3) + n + n + n + n  
  221. CC(n) = n(3n + 3) + n(25n - 3) + 6n + 5  
  222. CC(n) = 3n^2 + 3n + 25n^2 - 3n + 6n + 5  
  223. CC(n) = 28n^2 + 6n + 5  
  224. CC(n) is O(n^2)  
  225.  
  226. ### destructor
  227. Let D(n) represent the number of operations needed
  228. ```cpp
  229. template <class TYPE>
  230. SimpleTable<TYPE>::~SimpleTable(){
  231.     if(records_){ // 1
  232.         int sz=numRecords(); // 1 + NR(n)
  233.         for(int i=0;i<sz;i++){ // 1 + n + n
  234.             remove(records_[0]->key_); // n + n + n(R(n))
  235.         }
  236.         delete [] records_; // 1
  237.     }
  238. }
  239. ```
  240.  
  241. D(n) = 1 + 1 + NR(n) + 1 + n + n + n + n + n(R(n)) + 1  
  242. D(n) = 1 + 1 + 3n + 3 + 1 + n + n + n + n + n(3n^2 + 17n + 6) + 1  
  243. D(n) = n(3n^2 + 17n + 6) + 7n + 7  
  244. D(n) = 3n^3 + 17n^2 + 13n + 7  
  245. D(n) is O(n^3)  
  246.  
  247. # Part B - A2 Improvements
  248.  
  249. ### Function(s) improved: One Argument Constructor
  250. The for loop initializing the new records can be avoided by using an initializer list when dynamically allocating the array.
  251.  
  252. ```cpp
  253. template <class TYPE>
  254. SimpleTable<TYPE>::SimpleTable(int capacity): Table<TYPE>(){
  255.     records_=new Record*[capacity] {nullptr};
  256.     capacity_=capacity;
  257.         // for(int i=0;i<capacity_;i++){
  258.         // records_[i]=nullptr;
  259.     // }
  260. }
  261. ```
  262.  
  263. ### Function(s) improved: numRecords(), and any function that calls numRecords()
  264. The number of records can be stored as a property in the class instead of calculating it each time the function is called
  265.  
  266. ```cpp
  267. template <class TYPE>
  268. int SimpleTable<TYPE>::numRecords() const{
  269.         // int rc=0;
  270.     // for(int i=0;records_[i]!=nullptr;i++){
  271.         // rc++;
  272.     // }
  273.     // return rc;
  274.     return size;
  275. }
  276. ```
  277.  
  278. ### Function(s) improved: Copy Constructor, Copy Assignment Operator
  279. The object being passed into function(s) is of type SimpleTable. Because we know SimpleTables are sorted, there's no need to call update. Instead we can do a simple deep copy.
  280.  
  281. ```cpp
  282. template <class TYPE>
  283. SimpleTable<TYPE>::SimpleTable(const SimpleTable<TYPE>& rhs){
  284.     records_=new Record*[rhs.capacity_];
  285.     capacity_=rhs.capacity_;
  286.     for(int i=0;i<rhs.numRecords();i++){
  287.                  // update(rhs.records_[i]->key_,rhs.records_[i]->data_);
  288.                  records_[i] = new Record(rhs.records_[i]->key_,rhs.records_[i]->data_);
  289.     }
  290. }
  291. ```
  292.  
  293. # Part A - A2 Analysis
  294.  
  295. ### numRecords()
  296. Let NR(n) represent the number of operations needed
  297. ```cpp
  298. template <class TYPE>
  299. int SimpleTable<TYPE>::numRecords() const{
  300.     int rc=0; // 1
  301.     for(int i=0;records_[i]!=nullptr;i++){ // 1 + n + n
  302.         rc++; // n
  303.     }
  304.     return rc; // 1
  305. }
  306. ```
  307. NR(n) = 1 + 1 + n + n + n + 1  
  308. NR(n) = 3n + 3  
  309. NR(n) is O(n)  
  310.  
  311. ### update() - if item does not exists so you need to add it as a new record, assume no grow() call is made
  312. Let U(n) represent the number of operations needed
  313. ```cpp
  314. template <class TYPE>
  315. void SimpleTable<TYPE>::update(const std::string& key, const TYPE& value){
  316.     int idx=-1; // 1
  317.     int size=numRecords(); // 1 + NR(n)
  318.     for(int i=0;i<size;i++){ // 1 + n + n
  319.         if(records_[i]->key_ == key){ // n + n
  320.                  idx=i;
  321.         }
  322.     }
  323.     if(idx==-1){ // 1
  324.         if(size == capacity_){ // 1
  325.             grow();
  326.         }
  327.         records_[size++]=new Record(key,value); // 1 + 1 + 1 + 2 (Record())
  328.         for(int i=size-1;i>0 && records_[i]->key_ < records_[i-1]->key_;i--){ // 2 + 8(n-1) + (n-1)
  329.             Record* tmp=records_[i]; // 2(n-1)
  330.             records_[i]=records_[i-1]; // 4(n-1)
  331.             records_[i-1]=tmp; // 3(n-1)
  332.         }
  333.     }
  334.     else{
  335.         records_[idx]->data_=value;
  336.     }
  337.  
  338. }
  339. ```
  340. U(n) = 1 + 1 + NR(n) + 1 + n + n + n + n + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 8(n-1) + (n-1) + 2(n-1) + 4(n-1) + 3(n-1)  
  341. U(n) = 1 + 1 + 3n + 3 + 1 + n + n + n + n + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 8(n-1) + (n-1) + 2(n-1) + 4(n-1) + 3(n-1)  
  342. U(n) = 7n + 18(n-1) + 15  
  343. U(n) = 7n + 18n + 15 - 18  
  344. U(n) = 25n - 3  
  345. U(n) is O(n)  
  346.  
  347. ### update() - if item does exists and you are just modifying what is there
  348. Let UE(n) represent the number of operations needed
  349. ```cpp
  350. template <class TYPE>
  351. void SimpleTable<TYPE>::update(const std::string& key, const TYPE& value){
  352.     int idx=-1; // 1
  353.     int size=numRecords(); // 1 + NR(n)
  354.     for(int i=0;i<size;i++){ // 1 + n + n
  355.         if(records_[i]->key_ == key){ // n + n
  356.             idx=i;
  357.         }
  358.     }
  359.     if(idx==-1){ // 1
  360.         if(size == capacity_){
  361.             grow();
  362.         }
  363.         records_[size++]=new Record(key,value);
  364.         for(int i=size-1;i>0 && records_[i]->key_ < records_[i-1]->key_;i--){
  365.             Record* tmp=records_[i];
  366.             records_[i]=records_[i-1];
  367.             records_[i-1]=tmp;
  368.         }
  369.     }
  370.     else{
  371.         records_[idx]->data_=value; // 1 + 1 + 1
  372.     }
  373.  
  374. }
  375. ```
  376. UE(n) = 1 + 1 + NR(n) + 1 + n + n + n + n + 1 + 1 + 1 + 1  
  377. UE(n) = 1 + 1 + 3n + 3 + 1 + n + n + n + n + 1 + 1 + 1 + 1  
  378. UE(n) = 7n + 7  
  379. UE(n) is O(n)  
  380.  
  381. ### find() - if item is there
  382. Let F(n) represent the number of operations needed
  383. ```cpp
  384. template <class TYPE>
  385. bool SimpleTable<TYPE>::find(const std::string& key, TYPE& value){
  386.     int idx=-1; // 1
  387.     for(int i=0;i<numRecords();i++){ // 1 + n + n(NR(n)) + n
  388.         if(records_[i]->key_ == key){ // n + n + n
  389.             idx=i; // 1
  390.         }
  391.     }
  392.     if(idx==-1) // 1
  393.         return false;
  394.     else{
  395.         value=records_[idx]->data_; // 1 + 1 + 1
  396.         return true; // 1
  397.     }
  398. }
  399. ```
  400. F(n) = 1 + 1 + n + n(NR(n)) + n + n + n + n + 1 + 1 + 1 + 1 + 1 + 1  
  401. F(n) = 1 + 1 + n + n(3n + 3) + n + n + n + n + 1 + 1 + 1 + 1 + 1 + 1  
  402. F(n) = 5n + n(3n + 3) + 8  
  403. F(n) = 5n + 3n^2 + 3n + 8  
  404. F(n) = 3n^2 + 8n + 8  
  405. F(n) is O(n^2)  
  406.  
  407. ### find() - if item is not there
  408. Let FN(n) represent the number of operations needed
  409. ```cpp
  410. template <class TYPE>
  411. bool SimpleTable<TYPE>::find(const std::string& key, TYPE& value){
  412.     int idx=-1; // 1
  413.     for(int i=0;i<numRecords();i++){ // 1 + n + n(NR(n)) + n
  414.         if(records_[i]->key_ == key){ // n + n + n
  415.             idx=i; // 1
  416.         }
  417.     }
  418.     if(idx==-1) // 1
  419.         return false; // 1
  420.     else{
  421.         value=records_[idx]->data_;
  422.         return true;
  423.     }
  424. }
  425. ```
  426. FN(n) = 1 + 1 + n + n(NR(n)) + n + n + n + n + 1 + 1 + 1  
  427. FN(n) = 1 + 1 + n + n(3n + 3) + n + n + n + n + 1 + 1 + 1  
  428. FN(n) = 5n + n(3n + 3) + 5  
  429. FN(n) = 5n + 3n^2 + 3n + 5  
  430. FN(n) = 3n^2 + 8n + 5  
  431. FN(n) is O(n^2)  
  432.  
  433. ### remove() - if item is there
  434. Let R(n) represent the number of operations needed
  435. ```cpp
  436. template <class TYPE>
  437. bool SimpleTable<TYPE>::remove(const std::string& key){
  438.     int idx=-1; // 1
  439.     for(int i=0;i<numRecords();i++){ // 1 + n + n(NR(n)) + n
  440.         if(records_[i]->key_ == key){ // n + n + n
  441.             idx=i; // 1
  442.         }
  443.     }
  444.     if(idx!=-1){ // 1
  445.         int size=numRecords();  // 1 + NR(n)
  446.         delete records_[idx]; // 1 + 1
  447.         for(int i=idx;i<size-1;i++){ // 1 + (n-1) + (n-1)
  448.             records_[i]=records_[i+1]; // 4(n-1)
  449.         }
  450.         records_[size-1]=nullptr; // 1 + 1 + 1
  451.         return true; // 1
  452.     }
  453.     else{
  454.         return false;
  455.     }
  456. }
  457. ```
  458. R(n) = 1 + 1 + n + n(NR(n)) + n + n + n + n + 1 + 1 + 1 + NR(n) + 1 + 1 + 1 + (n-1) + (n-1) + 4(n-1) + 1 + 1 + 1 + 1  
  459. R(n) = 1 + 1 + n + n(3n + 3) + n + n + n + n + 1 + 1 + 1 + 3n + 3 + 1 + 1 + 1 + (n-1) + (n-1) + 4(n-1) + 1 + 1 + 1 + 1  
  460. R(n) = 8n + 6(n-1) + 12 + n(3n + 3)  
  461. R(n) = 8n + 6(n-1) + 12 + 3n^2 + 3n  
  462. R(n) = 8n + 6n + 12 + 3n^2 + 3n - 6  
  463. R(n) = 3n^2 + 17n + 6  
  464. R(n) is O(n^2)  
  465.  
  466. ### remove() - if item is not there
  467. Let RN(n) represent the number of operations needed
  468. ```cpp
  469. template <class TYPE>
  470. bool SimpleTable<TYPE>::remove(const std::string& key){
  471.     int idx=-1; // 1
  472.     for(int i=0;i<numRecords();i++){ // 1 + n + n(NR(n)) + n
  473.         if(records_[i]->key_ == key){ // n + n + n
  474.             idx=i; // 1
  475.         }
  476.     }
  477.     if(idx!=-1){ // 1
  478.         int size=numRecords();
  479.         delete records_[idx];
  480.         for(int i=idx;i<size-1;i++){
  481.             records_[i]=records_[i+1];
  482.         }
  483.         records_[size-1]=nullptr;
  484.         return true;
  485.     }
  486.     else{
  487.         return false; // 1
  488.     }
  489. }
  490. ```
  491. RN(n) = 1 + 1 + n + n(NR(n)) + n + n + n + n + 1 + 1 + 1  
  492. RN(n) = 1 + 1 + n + n(3n + 3) + n + n + n + n + 1 + 1 + 1  
  493. RN(n) = n(3n + 3) + 5n + 5  
  494. RN(n) = 3n^2 + 3n + 5n + 5  
  495. RN(n) = 3n^2 + 8n + 5  
  496. RN(n) is O(n^2)  
  497.  
  498. ### copy constructor
  499. Let CC(n) represent the number of operations needed
  500. ```cpp
  501. template <class TYPE>
  502. SimpleTable<TYPE>::SimpleTable(const SimpleTable<TYPE>& rhs){
  503.     records_=new Record*[rhs.capacity_]; // 1 + 1 + 1
  504.     capacity_=rhs.capacity_; // 1
  505.     for(int i=0;i<rhs.numRecords();i++){ // 1 + n + n(NR(n)) + n
  506.         update(rhs.records_[i]->key_,rhs.records_[i]->data_); // n(U(n)) + n + n + n + n
  507.     }
  508. }
  509. ```
  510.  
  511. CC(n) = 1 + 1 + 1 + 1 + 1 + n + n(NR(n)) + n + n(U(n)) + n + n + n + n  
  512. CC(n) = 1 + 1 + 1 + 1 + 1 + n + n(3n + 3) + n + n(25n - 3) + n + n + n + n  
  513. CC(n) = n(3n + 3) + n(25n - 3) + 6n + 5  
  514. CC(n) = 3n^2 + 3n + 25n^2 - 3n + 6n + 5  
  515. CC(n) = 28n^2 + 6n + 5  
  516. CC(n) is O(n^2)  
  517.  
  518. ### destructor
  519. Let D(n) represent the number of operations needed
  520. ```cpp
  521. template <class TYPE>
  522. SimpleTable<TYPE>::~SimpleTable(){
  523.     if(records_){ // 1
  524.         int sz=numRecords(); // 1 + NR(n)
  525.         for(int i=0;i<sz;i++){ // 1 + n + n
  526.             remove(records_[0]->key_); // n + n + n(R(n))
  527.         }
  528.         delete [] records_; // 1
  529.     }
  530. }
  531. ```
  532.  
  533. D(n) = 1 + 1 + NR(n) + 1 + n + n + n + n + n(R(n)) + 1  
  534. D(n) = 1 + 1 + 3n + 3 + 1 + n + n + n + n + n(3n^2 + 17n + 6) + 1  
  535. D(n) = n(3n^2 + 17n + 6) + 7n + 7  
  536. D(n) = 3n^3 + 17n^2 + 13n + 7  
  537. D(n) is O(n^3)  
  538.  
  539. # Part B - A2 Improvements
  540.  
  541. ### Function(s) improved: One Argument Constructor
  542. The for loop initializing the new records can be avoided by using an initializer list when dynamically allocating the array.
  543.  
  544. ```cpp
  545. template <class TYPE>
  546. SimpleTable<TYPE>::SimpleTable(int capacity): Table<TYPE>(){
  547.     records_=new Record*[capacity] {nullptr};
  548.     capacity_=capacity;
  549.        // for(int i=0;i<capacity_;i++){
  550.         // records_[i]=nullptr;
  551.     // }
  552. }
  553. ```
  554.  
  555. ### Function(s) improved: numRecords(), and any function that calls numRecords()
  556. The number of records can be stored as a property in the class instead of calculating it each time the function is called
  557.  
  558. ```cpp
  559. template <class TYPE>
  560. int SimpleTable<TYPE>::numRecords() const{
  561.        // int rc=0;
  562.     // for(int i=0;records_[i]!=nullptr;i++){
  563.         // rc++;
  564.     // }
  565.     // return rc;
  566.     return size;
  567. }
  568. ```
  569.  
  570. ### Function(s) improved: Copy Constructor, Copy Assignment Operator
  571. The object being passed into function(s) is of type SimpleTable. Because we know SimpleTables are sorted, there's no need to call update. Instead we can do a simple deep copy.
  572.  
  573. ```cpp
  574. template <class TYPE>
  575. SimpleTable<TYPE>::SimpleTable(const SimpleTable<TYPE>& rhs){
  576.     records_=new Record*[rhs.capacity_];
  577.     capacity_=rhs.capacity_;
  578.     for(int i=0;i<rhs.numRecords();i++){
  579.                   // update(rhs.records_[i]->key_,rhs.records_[i]->data_);
  580.                   records_[i] = new Record(rhs.records_[i]->key_,rhs.records_[i]->data_);
  581.     }
  582. }
  583. ```
  584.  
  585.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!