Question

What is the time complexity of my algorithm? It uses an vector E that contains and object made of a string and an integer. It takes an empty vector as parameter and returns the vector with the top three integers from the objects in E .

void Trendtracker::top_three_trends(vector<string> &T) {
   T.clear();
   if (E.size() == 0) {
       return;
   }

   if (E.size() == 1) {
       T.push_back(E[0].hashtag);
   }

   else if (E.size() == 2) {
       if (E[0].pop > E[1].pop) {
           T.push_back(E[0].hashtag);
           T.push_back(E[1].hashtag);
       }
       else {
           T.push_back(E[1].hashtag);
           T.push_back(E[0].hashtag);
       }
   }
   else {
       vector<Entry> temp;
       temp = E;

       for (int i = 0; i < 3; i++) {
           int topPop = temp[0].pop;
           string topHashtag = temp[0].hashtag;
           int index = 0;
           for (int j = 1; j < temp.size(); j++) {
               if (temp[j].pop > topPop) {
                   topPop = temp[j].pop;
                   topHashtag = temp[j].hashtag;
                   index = j;
               }
           }
           T.push_back(topHashtag);
           temp.erase(temp.begin() + index);
      
       }
   }

}

Answer 1

void Trendtracker::top_three_trends(vector<string> &T) {
T.clear();//O(1)
if (E.size() == 0) //O(1)
{
return;//O(1)
}

if (E.size() == 1) //O(1)
{
T.push_back(E[0].hashtag);//O(1)
}

else if (E.size() == 2) //O(1)
{
if (E[0].pop > E[1].pop) //O(1)
   {
T.push_back(E[0].hashtag);//O(1)
T.push_back(E[1].hashtag);//O(1)
}
else
   {
T.push_back(E[1].hashtag);//O(1)
T.push_back(E[0].hashtag);//O(1)
}
}
else {
vector<Entry> temp;//O(1)
temp = E;//O(1)

for (int i = 0; i < 3; i++) //O(3) =O(1)
   {
int topPop = temp[0].pop;//O(1)
string topHashtag = temp[0].hashtag;//O(1)
int index = 0;//O(1)
for (int j = 1; j < temp.size(); j++)//O(n) //n is size of temp
       {
if (temp[j].pop > topPop)//O(1) //runs n times
           {
topPop = temp[j].pop;//O(1)
topHashtag = temp[j].hashtag;//O(1)
index = j;//O(1)
}
}
T.push_back(topHashtag);//O(1)
temp.erase(temp.begin() + index);//O(1)
  
}
}

}

Total complexity : O(n)//worst case
best case :O(1)