Question

5. i) Describe an algorithm that, upon input of a number n given in base 10, outputs the digits of n in base 8, starting from the rightmost. Esrample: If you are given the number 156, the output will be 432, because (156) 10 = (234)s. ii) What will be the complexity of the algorithm? You may assume that performing the division algorithm upon two numbers to find the quotient and remainder is the basic operation. (As a challenge, you can break up the division algorithm into multiplying, comparing, and then subtracting, and then see how it impacts the complexity.)

Discrete Mathematics

Answer 1

5. i)

octal=0 Algo dectooctal (n): while (nl=0) octal & (n.1-8). no; octal is 10; retorn octal

ii)The complexity is log₈n

9.

i)7,3,4,1,6

1. 3,7,4,1,6

2. 3,4,7,1,6

3. 3,4,1,7,6

4. 3,4,1,6,7

5. 3,4,1,6,7

6. 3,1,4,6,7

7. 3,1,4,6,7

8. 1,3,4,6,7

9. 1,3,4,6,7

The total setps involved are 9 in case of bubble sort.

ii)

7 3,4, 1,6 7,3 4,1,6 1,6 4 7 3 6 3,7 16 1,4,6 1,3,4,6,7

The number of steps is 11, including divide and conquer operations.

**Kindly upvote if you like the answer. thank you