hello, I don\'t need the other questions solved, just b) where it asks to do a h

Question

hello, I don't need the other questions solved, just b) where it asks to do a hand trace and d) where it asks to check on space complexity. My values are not making sense. Could someone do it step by step?

Question 4 Consider the algorithm DoSomething below Algorithm DoSomething (A, n) Input: Array A of integer containing n elements Output: Array M of integer containing n elements I. fori-0 to n-1 do 2. Zomfi]-0 3. end for 4. fori-0 to n-2 do 5. forj-i+l ton-1 do 6. ifAiA then 7. 8. 9. 10. end if 1I. end for 12. end for 13. for i 0 to n-1 do 14. MIZomil-Ai] 15. end for 16. Return M Zom [jl- Zom l+1 else Zomli]- Zomfil+I a) What is the big-O (O(n)) and big-Omega ((n) time complexity for algorithm DoSomething in terms of n? Show all necessary steps. b) Trace (hand-run) DoSomething for an array A (71,15,45,98,04,32). What is the resulting M? c) What does DoSomething do? Explain that clearly and briefly given any arbitrary array A of n d) Can the runtime of DoSomething be improved easily? Explain how (i.e. re-write another e) Can the space complexity of DoSomething be improved? Explain how? integers? solution(s) that does exactly what DoSomething is doing more efficiently)?

Explanation / Answer

Z- 0 0 0 0 0 0 - i = 0
   4 0 0 1 0 0 - i = 1
   4 1 1 2 0 1 - i = 2
   4 1 3 3 0 1 - i = 3
   4 1 3 5 0 1 - i = 4
   4 1 3 5 0 2 - i = 5

So M = 04,15,32,45,71,98

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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