Question #193578

Identify two problems in each category of the following time complexities and derive the complexity of these identified problems. (4+6 marks) O(n log n), and O(n2 ).


1
Expert's answer
2021-05-18T06:01:02-0400

O(n log n): Comparison sort, Fast Fourier transform

O(n2^2): Bubble sort, Insertion sort


Comparison sort: you must look at every element which is O(n). For each of those elements you look at, you must find out if its in the right order, which is at best O(log n) (binary search for example). So the net sum becomes O(n log n).

Fast Fourier transform: every sum has O(1)O(1) complexity. The number of iterations: O(n),O(2n2),O(44n)...O(n),O(2\cdot\frac{n}{2}),O(4\cdot\frac{4}{n})... So, every step has the complexity O(n)O(n). We have log2nlog_2n steps, so the complexity of algorithm will be O(nlogn)O(nlogn).


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS