Task $2$: The following section of a list implementation is given.

Calculate the runtime of the call to function g$.$ Calculate the runtime in the best, average and

worst case. Also state the runtime of the function in O$-$notation. Can you give an alternative

shorter implementation that calculates the same? Exercise $3$ The following function fun is given.

Calculate the runtime of the fun function call. To do this, set up the recurrence relation and

resolve it into a closed form. Exercise $4$: Three simple functions fun$1,$ fun $2$ and fun $3$ are given.

Do the functions each calculate the same thing? If not, what is the difference? Is there a

precondition for which the functions all do the same thing?

The input variable is $n,$ the number of values in the int f$1$eld is a$.$ What is the best

and worst case for each function? Specify the complexity in the best and worst case for

each function $($without calculating$)$ and justify each with a sentence.Task $5$: Two functions fun$1$ and fun$2$ are given. The input variable $n$ isthe number of

values in the int fleld a$.$ Each arithmetic operation is a step.

Do the functions each do the same thing? If not, what is the difference?

Yes, the functions do the same thing. The addition is replaced by successive incrementing,

but has the same effect.

What is the complexity for funl and fun$2?$

Both are $O(n)$ by the choice of input size, i$.$e$.$ the number of elements.

For which function do you expect a longer runtime and under what conditions?

A higher runtime $($not complexity$)$ is to be expected with fun$2$ when large numbers occur, as

it then requires many more steps $($arithmetic operations$).$

Evaluate the choice of input size for fun$2.$ What would be an alternative choice for the input

size?

The size of the coefficients would be more suitable as an input variable. The number of

significant bits of all coefficients or the sum of the coefficients could be considered, as this

has an influence on the number of steps.Task $1$: The program code of SelectionSort $($sorting by selection$)$ is given.

Calculate the runtime of the selsort function call. Calculate the runtime in the worst case. Also

enter the runtime of the function in $O$ notation.