Will Kallander CSSAP443 05 April 2001 Run Time Analyses --------------------------------------------------------------------------------- Part C: Requesting free memory: MemoryManager.malloc() MemoryManager.malloc() running time depends on DoubleLinkList.removeFirst(). int DoubleLinkList.removeFirst() { Cost Times int nodePtr = m_head; 1 1 if( !isEmpty() ) // same as m_head == NUL 1 1 if( m_tail == m_head ) { 1 1 m_tail = m_head = NIL; // two operations! 2 1 } else { m_head = ListNode.getNext( m_head ); 1 1 ListNode.setPrevious( m_head, NIL ); 1 1 } return nodePtr; 1 1 } int MemoryManager.malloc() { Cost Times return( m_freeMemory.removeFirst() ); 1 1 } T(n) of DoubleLinkList.removeFirst() = 8. T(n) MemoryManager.malloc() = 1 * T(n) of DoubleLinkList.removeFirst() = 1 * 8 = 8. So, this is a O(1) operation Returning free memory: MemoryManager.free(int) MemoryManager.free(int) running time depends on DoubleLinkList.insertLast(int). void DoubleLinkList.insertLast( int nodePtr ) { Cost Times if( m_tail != NIL ) { 1 1 ListNode.setPrevious( nodePtr, m_tail ); 1 1 ListNode.setNext( nodePtr, NIL ); 1 1 ListNode.setNext( m_tail, nodePtr ); 1 1 m_tail = nodePtr; 1 1 } else { ListNode.setNext( nodePtr, m_tail ); 1 1 ListNode.setPrevious( nodePtr, m_head ); 1 1 m_tail = m_head = nodePtr; 2 1 } } void MemoryManager.free( int ptr ) { Cost Times ListNode.setID( ptr, NIL ); 1 1 ListNode.setDataSize( ptr, 0 ); 1 1 m_freeMemory.insertLast( ptr ); 1 1 } T(n) of DoubleLinkList.insertLast(int) = 9. T(n) MemoryManager.free(int) = 1 * T(n) of DoubleLinkList.insertLast(int) + 2 = 1 * 9 + 2 = 11. So, this is a O(1) operation as well --------------------------------------------------------------------------------- Part D: LookupQueue constructor running time depends on DoubleLinkList constructor. public DoubleLinkList() { Cost Times m_head = m_tail = NIL; 2 1 } public LookupQueue() { Cost Times m_list = new DoubleLinkList(); 1 1 } T(n) of DoubleLinkList() = 2. T(n) of LookupQueue() = 1 * T(n) of DoubleLinkList() = 1 * 2 = 2. So, this is a O(1) operation ------------------------------- LookupQueue.enqueue(int) depends on DoubleLinkList.insertLast(int). T(n) of DoubleLinkList.insertLast(int) from above = 8. void LookupQueue.enqueue( int element ) { Cost Times m_list.insertLast( element ); 1 1 } T(n) of LookupQueue.enqueue(int) = 1 * T(n) of DoubleLinkList.insertLast(int) = 1 * 8 = 8. So, this is a O(1) operation ------------------------------- LookupQueue.dequeue() depends on DoubleLinkList.removeFirst(). T(n) of DoubleLinkList.removeFirst() from above = 9. int LookupQueue.dequeue() { Cost Times return( m_list.removeFirst() ); 1 1 } T(n) of LookupQueue.dequeue() = 1 * T(n) of DoubleLinkList.removeFirst() = 1 * 9 = 9. So, this is a O(1) operation ------------------------------- LookupQueue.dequeue(int) depends on DoubleLinkList.remove(int). int DoubleLinkList.remove( int id ) { Cost Times int nodePtr = m_head; 1 1 for(; NIL != nodePtr; 2 n nodePtr = ListNode.getNext(nodePtr) ) { if( id == ListNode.getID(nodePtr) ) { 1 n if( nodePtr == m_head ) { 1 n if( m_tail == m_head ) { 1 n m_tail = m_head = NIL; 1 n } else { m_head = ListNode.getNext( nodePtr ); 1 n ListNode.setPrevious( m_head, NIL ); 1 n } } else { if( nodePtr == m_tail ) { 1 n m_tail = ListNode.getPrevious( m_tail ); 1 n ListNode.setNext( m_tail, NIL ); 1 n } else { int prev = ListNode.getPrevious(nodePtr); 1 n int next = ListNode.getNext( nodePtr ); 1 n ListNode.setNext( prev, next ); 1 n ListNode.setPrevious( next, prev ); 1 n } } break; 1 1 } } return nodePtr; 1 1 } public int dequeue( int id ) { Cost Times return( m_list.remove(id) ); 1 1 } T(n) of DoubleLinkList.remove(int) = 3 + (15 * n) = 15n + 3 T(n) of LookupQueue.dequeue() = 1 * T(n) of DoubleLinkList.remove(int) = (1 * 1) * 15n + 3. = 15n + 3. So, this is a O(n) operation ------------------------------- LookupQueue.print() depends on DoubleLinkList.print(). void DoubleLinkList.print( String name ) { Cost Times System.out.println( "Content of the " 1 1 + name + "-List: Head(" + m_head + ")" ); int nodePtr = m_head; 1 1 while( NIL != nodePtr ) { 1 n int id = ListNode.getID( nodePtr ); 1 n int prev = ListNode.getPrevious( nodePtr ); 1 n int next = ListNode.getNext( nodePtr ); 1 n System.out.print( " " + nodePtr + "[" + id 1 n + " " + prev + " " + next + "]: " ); int length = ListNode.getDataSize( nodePtr ); 1 n for( int i = 0; 1 n i < length; ++i ) { 2 n * m System.out.print( ListNode.getData(nodePtr, i) + " " ); 2 n * m } System.out.println(); 1 n nodePtr = ListNode.getNext( nodePtr ); 1 n } } void LookupQueue.print() { Cost Times m_list.print( "LookupQueue" ); 1 1 } n = number of elements in list m = memory chunksize - 4 T(n) of DoubleLinkList.print() = 2 + (9 * n) + (4 * n * m) = 9n + 4nm + 2 T(n) of LookupQueue.print() = 1 * T(n) of DoubleLinkList.print() = 1 * 9n + 4nm + 2 = 9n + 4nm + 2 So, this is a O(n * m) operation ---------------------------------------------------------------------------------