8. (8 points) What is transitivity property for notation ? Prove that notation h

Question

8. (8 points) What is transitivity property for notation ? Prove that notation holds the transitivity 9. (8 points) 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 split(string text, string delimiter) vector pieces; int location text.find (delimiter); int start-e //while we find something interesting while (location != string: :npos){ //build substring string piece = text.substr(start, location - start); pieces.push_back(piece); start = location + 1; //find again location-text.find(delimiter, start) string piece-text . substr(start, location - start); pieces.pushback(piece); return pieces;

Explanation / Answer

Hey,

Below are the answers to your questions

8)

To prove the transitivity of theta(n), it should be proved that

if theta(g(n))=f(n), theta(h(n))=g(n) then theta(h(n))=f(n)

For theta(g(n))=f(n),  0 =< c1*g(n) =<f(n) =< c2*g(n) is true------eq2

theta(h(n))=g(n) 0 =< c3*h(n) =<g(n)=< c4*h(n) is true------eq1

Multiply eq1 and eq2

So, 0 =< c3*h(n)*g(n)*c1 =<g(n)*f(n)=< c4*h(n)*g(n)*c2

0 =< C1*h(n) =<f(n)=< C2*h(n)-------------eq3

So, eq3 states that f(n)=theta(h(n))

9)

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)

Kindly revert for any queries, will be waiting for your positive feedback.:)

Thanks.

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

---

---

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