Through analysis argue whether the experimental data gathered from these map implementations supports Big O analyses. The experimental data is structured as follows:
Total number of key-value pairs operated on. Both the "Existing" and "Miss" experiments also Describes both the map type use this number of trials and the class of problem within that type Total number of comparison to complete all insertions Binary Tree: :Unbalanced : :Insert : : [Total KVPs - 196, Total Compares - 11540] :: Search: : Existing: : [Max Compares = 135, Average Compares = 59. 87244897959184] 4:Search: : Miss:>>[Max Compares = 135, Average Compares = 66. 45918367346938] The map operation and any modifiers. For example, "Existing" means matching of keys that do exist while "Miss" means The average number of comparisons attempting to match keys that do not exist for a single search. This average is (in other words the worst case) derived from the total count of The maximum number of comparisons comparisons for all searches. needed in all of the search attempts. For example, while we searched over 196 keys in the tree, the worst case for this example required 135 compares to determine that the key did not existBinary Tree: : Unbalanced : : Insert: : [Total KVPs = 196, Total Compares = 11540] :: Search: :Existing: : [Max Compares = 135, Average Compares = 59. 87244897959184] :: Search: :Miss: : [Max Compares = 135, Average Compares = 66. 45918367346938] Binary Tree: : Balanced : : Insert: : [Total KVPs = 196, Total Compares = 1202] :: Search: : Existing: : [Max Compares = 8, Average Compares = 6.739795918367347] :: Search: :Miss: : [Max Compares = 8, Average Compares = 7.6938775510204085] HashTable: :10 Buckets : : Insert: : [Total KVPs = 196, Total Compares = 1925] : : Search: :Existing: : [Max Compares = 28, Average Compares = 10. 770408163265307] :: Search: :Miss: : [Max Compares = 28, Average Compares = 19. 653061224489797] HashTable: :100 Buckets : : Insert: : [Total KVPs = 196, Total Compares = 280] : : Search: :Existing: : [Max Compares = 5, Average Compares = 1. 9948979591836735] : : Search: :Miss: : [Max Compares = 5, Average Compares = 1. 9183673469387754] HashTable: : 196 Buckets : : Insert: : [Total KVPs = 196, Total Compares = 218] : : Search: :Existing: : [Max Compares = 6, Average Compares = 1 . 489795918367347] : : Search: :Miss: : [Max Compares = 6, Average Compares = 1 . 0357142857142858] HashTable: :1000 Buckets : : Insert: : [Total KVPs = 196, Total Compares = 197] :: Search: : Existing: : [Max Compares = 3, Average Compares = 1 .1020408163265305] : : Search: :Miss: : (Max Compares = 2, Average Compares = 0. 23469387755102042]