-2
$\begingroup$
  1. Can we use recursive algorithm to find the greatest element of a finite list when numbers are unsorted.
  2. How to use recursive algorithm to find the least element of a finite list of unsorted numbers where repetitions of number is allowed.
  3. How can Mergesort calls itself n^2 times on a list with n numbers.
  4. Is it true if the input list has only 3 numbers, then Mergesort does not need the merging step.
  5. Can we find number of elements in a finite list with a recursive algorithm.

Little explanations will be helpful to understand, thank you.

$\endgroup$
  • 1
    $\begingroup$ We're not here to do your homework. $\endgroup$ – orlp Dec 16 '18 at 4:46
  • 1
    $\begingroup$ its not a homework $\endgroup$ – JKLM Dec 16 '18 at 4:57
1
$\begingroup$

It'll be hard to understand numbers 3 and 4 until you're solid on the others. I'd suggest looking closely at the definition of recursion. A solid understanding of recursion is crucial to a lot of computer science.

But for answers, if it helps at all:

Can we use recursive algorithm to find the greatest element of a finite list when numbers are unsorted.

def greatest(list):
    first = list[0]
    remaining = list[1:]
    if remaining exists:
        return max(first, greatest(remaining))
    else:
        return first

How to use recursive algorithm to find the least element of a finite list of unsorted numbers where repetitions of number is allowed.

Exactly the same as above, but use min instead of max.

How can Mergesort calls itself n^2 times on a list with n numbers.

It doesn't. Mergesort runs in $O(n \log n)$. Are you thinking of Quicksort?

Is it true if the input list has only 3 numbers, then Mergesort does not need the merging step.

Depends on your implementation. The simple cases of algorithms, when $n$ is so far, tend not to be interesting—but have a lot of potential for bugs. So if I were writing Mergesort, I'd start with something like "if you have less than five numbers, do it by brute force (which is $O(1)$ since we have an upper bound on $n$)".

Can we find number of elements in a finite list with a recursive algorithm.

def count_elements(list):
    if list does not exist: return 0
    return 1 + count_elements(list[1:])
$\endgroup$
  • $\begingroup$ Thank you, so for 4th point, it's not true unless you use brute force? $\endgroup$ – JKLM Dec 16 '18 at 16:40
  • 1
    $\begingroup$ @JKLM It depends on your implementation. If I were implementing it, I'd use brute force for that particular case. Others might do it differently. $\endgroup$ – Draconis Dec 16 '18 at 16:53
  • $\begingroup$ so theroticallly it does not need that merging step? $\endgroup$ – JKLM Dec 16 '18 at 17:03
  • 1
    $\begingroup$ @JKLM Again, it depends on your implementation. Some implementations would use a merging step there, while others wouldn't. $\endgroup$ – Draconis Dec 16 '18 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.