Consider the following algorithm, given some input vector x of length n. total-3

Question

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) n = n-1; else total = total - x(n) end end (a) Derive in Big-O notation, the computational cost of the algorithm. Hints: 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 r ning the algorithm above, what would be the Big-O complexity of the overall algorithm?

Explanation / Answer

a)

1) the worst case is when all elements in vector X are positive

so the code of   "if" statement excutes and n is decremented by only one in each iteration

2) In worst case loop will be invoked by "n" times

3) Total no of operations in worst case is 2n

4) In big O notation the worst case complexicity is given by 0(n)

b) By applying sorting we can arrange element in an order so all negitive elements come together and else part code will excuit till positive numbers reached after that if part code will excuites

so over all time complexicity of algorithm increses due to sorting

the quicksort worst case complexity + code time complexity

i.e 0(logn) + 0(n)

overall complexicity is 0(logn)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---