Hi, For the question below it is exercise 30 in section 4.3 of discrete mathemat

Question

Hi,

For the question below it is exercise 30 in section 4.3 of discrete mathematics by johnsonbaugh

The area that I have problem with is the begining. It says when is even and odd. for line 2 to line 5,

do I ignore that since  that is if n = 1

Should I put a number for m and use induction?

30. Find the exact number of comparisons (lines 10, 15, 17, 24,

and 26) required by the following algorithm when n is even

and when n is odd. Find a theta notation for this algorithm.

Input:  s1, s2, . . . , sn, n

Output:  large (the largest item in s1, s2, . . . , sn), small

(the smallest item in s1, s2, . . . , sn)

1.  large small(s, n, large, small) {

2.  if (n == 1) {

3. large = s1

4. small = s1

5. return

6.  }

7.  m = 2n/2

8.  i = 1

9.  while (i ? m ? 1) {

10. if (si  > si +1)

11. swap(si , si +1)

12. i = i + 2

13.  }

14.  if (n > m) {

15. if (sm ?1 > sn)

16. swap(sm ?1, sn)

17. if (sn > sm)

18. swap(sm, sn)

19.  }

20.  small = s1

21.  large = s2

22.  i = 3

23.  while (i ? m ? 1) {

24. if (si  < small)

25. small = si

26. if (si +1 > large)

27. large = si +1

28. i = i + 2

29.  }

30.  }

Explanation / Answer

dont ignore that n == 1 part.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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