Question

Please provide the big oh notation for running time and space complexity for the following functions (available, into, out, size, and printAll):

int

SplayTreeInventory::available(string id){  

Node* temp=stmap->findSplay(id);

if(temp!=NULL)

return temp->value;

else

return -1;  

}

void

SplayTreeInventory::into(string id, int amount)

{

Node* temp=stmap->findSplay(id);

if(temp==NULL){

stmap->putSplay(id, amount);

}

else{

temp->key+=amount;

}

}

void

SplayTreeInventory::out(string id, int amount)

{

Node* temp=stmap->findSplay(id);

if(temp==NULL){

}

else{

if(temp->value<=amount)

stmap->erase(id);

else

temp->value-=amount;

}

}

int

SplayTreeInventory::size()

{

return stmap->size();

}

void

SplayTreeInventory::printAll()

{

printAllHelper(this->stmap->root);

}

Answer 1

int SplayTreeInventory::available(string id){  

Node* temp=stmap->findSplay(id); //constant

if(temp!=NULL) //constant

return temp->value; //constant

else

return -1; //constant

}

Constant time and space ----- O(1)

------------------------------------------

void SplayTreeInventory::into(string id, int amount){

Node* temp=stmap->findSplay(id); //same as findSplay

if(temp==NULL){ //constant

stmap->putSplay(id, amount); //same as putSplay

}

else{

temp->key+=amount; //constant

}

}

Time complexity = O(max(findSplay,putSplay))

Space complexity = O(max(findSplay,putSplay))

---------------------------------------------

void SplayTreeInventory::out(string id, int amount){
Node* temp=stmap->findSplay(id); //same as findsplay

if(temp==NULL){ //constant
}
else{
if(temp->value<=amount) //constant
stmap->erase(id); //same as erase
else
temp->value-=amount; //constant
}
}

Time Complexity = O(erase)
Space Complexity = O(erase)

-------------------------------------------------

int SplayTreeInventory::size(){
return stmap->size();
}
Time and space O(1)
----------------------------

void SplayTreeInventory::printAll(){
printAllHelper(this->stmap->root);
}
Time and Space are same as printHelper
----------------------------