$4.(25$ points$)$ Design and write the pseudocode for an algorithm to rearrange elements of a given array of $\backslash ($ n $\backslash )$ real numbers so that all its negative elements precede all its positive elements. You should use an extra array of the same size with the input array in your algorithm, $($i$.$e$.,$ the space complexity of the algorithm, considering the input itself as an intrinsic part of the problem and hence we assume that it does not contribute to the space complexity$),$ should be linear $\backslash ((\backslash$theta$($n$))\backslash ).$ Your algorithm should work in linear time complexity as well. Prove that the time complexity of your algorithm is $\backslash (\backslash$theta$($n$)\backslash ).$ What about best case, and average case time complexities?