in at least 300 words describe the algorithm used below and it\'s complexity . R
ID: 3768722 • Letter: I
Question
in at least 300 words describe the algorithm used below and it's complexity. Restrain from describing what the code does unless it support the description of the algorithm or complexity.
(define largest(lambda (lst sum size)
(cond
((null? lst)(if (= sum 0) size 0))
(else (if (> (largest (cdr lst) (+ sum (car lst)) (+ size 1)) /*Sum with item*/
. (largest (cdr lst) sum size)) /*Sum without item*/
(largest (cdr lst) (+ sum (car lst)) (+ size 1)) /*sum w/items*/
(largest (cdr lst) sum size)))))) /*Return sum without items*/
Explanation / Answer
This algorithm is based on recursive function. recursive function is one which call itself.
Normally to store values, it uses stacks.
Coming to our recursive function parameter are list with data, sum variable to hold the sum of data,
and another variable is size , which is to hold the value of length of list that is passes to
function. Function name is largest. it returns the largest element on the given list.
Every time it calculates sum of integers that we are parsing, as well as it saves the largest
element found in the list of numbers that we parsed.
Firstly we will check for whether size is 0 or not. if size is 0 , then it means that
all numbers in list are processed. Then it returns that value to calling function.
if not size zero , then it adding sum with item and without item and comparing values.
and storing the values, and decremented size and calling recursively this function
itself until all values passed. here with items and without items, both ways we are calling
recursively same function. Each time it stores the values of every iteration in a variable. Of course internally these values are
stored in stack pointers. That's why one should take care of terminating condition, otherwise it will call infinite times and may cause error of stack out of bounds error.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.