In C$++,$ put everything in one program to prevent any confusion. Problem $4$: $(25$ Points$)$

Suppose you are given an array, A$,$ containing $n$ distinct integers that are listed in increasing order.

Given a number k:

$4\mathrm{.}1$: describe a recursive algorithm to find two integers in A that sum to $k,$ if such a pair exists.

Submit your programming code in PDF$.$

$4\mathrm{.}2$: Write $1$ non$-$recursive method $($Java$,$ C$++,$ Python$).$ Submit your programming code in PDF$.$

$4\mathrm{.}3$: Give running times of both algorithms in Big$-O$ on an array of $n$ values. $($see details at the

bottom$)$

$4\mathrm{.}4$: Construct a table of actual running times of both algorithms by writing programs in the

programming language of your choice $($Java$,$ C$++,$ Python$).($See details at the bottom$)$

a$)$ with array sizes of $10,100,$ and $1000.$

b$)$ populate an array with a random number generator.

c$)$ save the program as Problem$4\_$Assignment$1\_$CIS$350\_$Fall$2023\_$YourName.xxx $($xxx should

replace with the program file extension$)$

Note: FAQ: Should we search for all pairs whose sum equals $k$ or should we stop after finding

the first pair $($assuming it exists$)?$ Additionally, how should we select a value for k$?$ Can we

choose any constant value, or should it be randomly generated as well?

Answer: You should search for just one and the first such pair. You can test with a fixed value of $k$

for which you know there is a pair whose sum is $k$ and also test with a random value of $k$ within a

reasonable range.