What is the run time of this algorithm? Input: A collection of integers Spectrum

Question

What is the run time of this algorithm?

Input: A collection of integers Spectrum NovelSpectrumConvolution(Spectrum) MaxMass leftarrow maximum integer in Spectrum Initialize an array Count of size MaxMass with all values = 0 Sort Spectrum in increasing order for each M1 in Spectrum for each M2 > M1 in Spectrum Diff leftarrow M2-M1 Count[Diff] leftarrow Count[Diff] + 1 ConvolutionSpectrum leftarrow empty set for 1 leftarrow 1 to MaxMass if Count[Diff] > 0 add (Diff, Count[Diff]) into ConxoIutionSpectrum//(mass, multiplicity) Sort ConvolutionSpectrum in decreasing order of the multiplicity Output ConvolutionSpectrum

Explanation / Answer

Let the size of the spectrum array be n. So the runtime of the algorithm is O(n^2).

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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