4. Consider the following algorithm, given some input vector x of length n. tota

Question

4. Consider the following algorithm, given some input vector x of length n. total = 30; while n> 0 if x(n) > 0 total - total + x(n) else total = total - x(n) n- n-2; end end (a) Derive in Big-O notation, the computational cost of the algorithm. Hints: e What is the worst case! In the worst case, how many times do we invoke the loop, and how many operations occur each time? » What is the total number of operations? . Convert your result to Big-O notation. b) If we use the sorting algorithm Quicksort on the vector x before calling run- ning the algorithm above, what would be the Big-O complexity of the overall algorithm?

Explanation / Answer

a)
Inside the while loop (a > 0),
if condition is executed if x(n)>0
else condition s executed if x(n)<=0

If condition execution will decrease the n by 1
else condition execution decreases n by 2

i) In worst case scenario,
the if condition runs every time
In each if condition, 2 FLOPS are performed (addition total=total+x(n) and subtraction n=n-1)

So the total number of flops is 30*2 = 60 is the worst case

ii) In worst case scenario,
the loop is invoked 30 times and each time 2 operations are formed

iii) Total number of operations is 30*2 = 60 is the worst case

iv) In big-O notation, we can say that the time required is O(2n) =O(n)

b) Depending on whether x(n) is negative or positive, In either case the time complexity would remain the same: O(n)

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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