Homework answers / question archive / Can you provide me the analysis of the below functions and their big O notations and also suggestions to improve their efficienty in part b

Can you provide me the analysis of the below functions and their big O notations and also suggestions to improve their efficienty in part b

Computer Science

Share With

---

Can you provide me the analysis of the below functions and their big O notations and also suggestions to improve their efficienty in part b. thank you.

#Part A: Analysis:

 

Given the SortedTable class:

```python

 

class SortedTable:

 

    # packaging the key-value pair into one object

    class Record:

        def __init__(self, key, value):

            self.key = key

            self.value = value

 

    def __init__(self, cap=32):

        # this initializes a list of of capacity length with None

        self.the_table = [None for i in range(cap)]

        self.cap = cap

 

    def insert(self, key, value):

        if (self.search(key)!=None):

            return False

 

        if(len(self) == self.cap):

            # increase the capacity if list is full

            new_table = [None for i in range(self.cap*2)]

            for i in range(self.cap):

                new_table[i]=self.the_table[i]

            self.the_table = new_table

            self.cap *= 2

 

        self.the_table[len(self)]=self.Record(key,value)

        size = len(self)

        for i in range (0,size-1):

            for j in range(0,size-1-i):

                if(self.the_table[j].key>self.the_table[j+1].key):

                    tmp=self.the_table[j]

                    self.the_table[j]=self.the_table[j+1]

                    self.the_table[j+1]=tmp

        return True

 

    def modify(self, key, value):

        i = 0

        while (i < len(self) and self.the_table[i].key != key):

            i+=1

        if(i==len(self)):

            return False

        else:

            self.the_table[i].value = value

            return True

 

    def remove(self, key):

        i = 0

        size = len(self)

        while (i < size and self.the_table[i].key != key):

            i+=1

        if(i==size):

            return False

        while(i+1 < size):

            self.the_table[i]=self.the_table[i+1]

            i+=1

        self.the_table[i] = None

        return True

 

    def search(self, key):

        i = 0

        size = len(self)

        while  i < size and self.the_table[i].key != key :

            i+=1

        if i==size:

            return None

        else:

            return self.the_table[i].value

 

    def capacity(self):

        return self.cap

 

    def __len__(self):

        i =0

        count = 0

        while(i < len(self.the_table)):

            if(self.the_table[i]!=None):

                count+=1

            i+=1

        return count

 

```

Analyze the functions in the above code that is listed below with respect to the number of records in the table.  Provide the final answer (in big-O notation) into the table.  Show your rough work by  a proper analysis below the summary table of the functions

 

## Summary table

 

| Function | run time with respect to number of records in table |

|---|---|

|def insert(self, key, value):| |

|def modify(self, key, value):| |

|def remove(self, key):| |

|def search(self, key):| |

|def capacity(self):| |

|def __len__(self):| |

 

## Analysis of  def insert(self, key, value):

 

## Analysis of def modify(self, key, value):

 

## Analysis of def remove(self, key):

 

## Analysis of def search(self, key):

 

## Analysis of def capacity(self):

 

## Analysis of def __len__(self):

 

# Part B: Improvements

Suggest 2 improvements you could make to the code that will improve its efficiency. State which function(s) would be improved by the suggested improvement.

Which improvements counts and which do not:

• You can't change the underlying data structure. For example, "make it a hash table" would make it something different so that won't count. Fundamentally it must use a sorted python list as the underlying data structure
• A change only counts once: "implementing a selection sort instead of what is written in the len() function" and "implementing selection sort instead of what is written in the capacity() function" is just one suggestion not two. (note this suggestion is silly, and just used as an example)
   

* Suggestion 1:

* Suggestion 2: