Consider the following code: rand() returns a random non-negative integer and ru

Question

Consider the following code:

rand() returns a random non-negative integer and runs in `O(1)` time. Assume that each possible unsigned int value is equally likely to be returned on any given call to rand().

Match the line numbers below to the closest correct complexity expression, giving the single-letter identifier for your chosen complexity.
A: O(1) B: O(log n) C: O(sqrt(n)) D: O(n) E: O(n log n) F: O(n sqrt(n)) G: O(n2)   H: O(n2 log(n)) I: O(n2 sqrt(n)) J: O(n3) K: none of these

If the line numbers are preceded by "Avg", give the average case complexity. Otherwise, give the worst case complexity.

Line 7: [L7]
Avg Line 7: [A7]
Lines 6-7: [L67]
Line 13: [L13]
Line 12: [L12]
Avg Line 12: [A12]
Lines 11-13: [L1113]
Avg Lines 11-13: [A1113]
Line 14: [L14]
Avg Line 14: [A14]

Please show all the work in detail. Thanks

Explanation / Answer

[L7] std::set is commonly implemented as a red-black binary search tree. Insertion on this data structure has a worst-case of O(log(n)) complexity. As the insertion takes O(log(n)) the inner sattement takes constant time, thus the complexity is O(log(n)). [L7] -> B

[A7] Same as above

[L67] Considering n starts from 0 to t.size()-1, the while loop will run n times and the statement [L7] inside while loop takes O(log(n)), thus total complexity of [L67] is O(nlog(n)) . [L67] -> E

[L13] list pushback takes constant time this the complexity is A

[L12] is an if statement of comparson thus constant A

[L1113] Line is a loop and goes from 0 to size of t thus its the loop will run n times (n is no of elements in t) and the remaining statements in loop are constant time statements thus the complexity is O(n) D

[L14] constant A

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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