What is the runtime complexity of Adam\'s famous string splitter code? Hint: Mak

Question

What is the runtime complexity of Adam's famous string splitter code? Hint: Make sure to look into the source code for string.find() in the C++ std library. I’ve included that code (downloaded from GNU).

static vector ring text string delimiter vector ring pieces int location text, (delimiter); inte start 0; //while we find something interesting while location string DRos)f build substring string piece text substr (start location start); (piece start location 1 //find again location ext find deli miter start); string piece text substr (start location start); pieseswRush bask (piece return pieces;

Explanation / Answer

Assumption is we have text length as N and we have N-1 delimeters in that text.

text.find() -->Takes O(n) time in the worst case to find the delimeter.

vector<string>pieces; -->O(1)
int location = text.find();delimeter-->At max O(n)
while(location!=string.pos()){ . -> Runs N times

string piece = text.substr(start,location-start); -->At max takes O(N) [Copying that many characters]*N times for while loop
start = location+1; -->O(1)
location = text.find(delimeter,start);-->At Max O(N) * N times for while loop

So While loop will run N time as we have N-1 delmieters and each time finding substr() and find() on an average will take O(n). So overall time complexity is O(N2)

}


Thanks, let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.