2. (a) Big-Oh notation provides a way to characterise the computational complexity of an algorithm. (0) In about 100 words, explain how you could estimate the computational complexity of an algorithm (i.e. its order expressed using Big-Oh notation) by analysing its pseudo-code description, without actually running the algorithm on a computer. [10%] () Imagine that you are now provided an executable file that implements an algorithm whose computational complexity needs to be characterised, but you do not have access to the source code. In about 100 words, explain how you could estimate the computational complexity of an algorithm by running the executable file. (10%) (b) Consider a mathematical series such that the number S, with index n (with n > 0) is defined as follows: Som 2 = 1 +2 +22 +2 +---+2* = i=0 The sequence of numbers in this series is therefore 1, 3, 7, 15, 31, 63, 127,... (0) Using iteration as the principal methodology, write a function that calculates the number in the series for a given index n. The function should take an integer n as input and return an integer. In your answer, use either pseudo- code or C code to describe the function. (10%) (1) Write a second function that calculates the number Sne in the series for a given index n using recursion this time. The function should again take an integer n as input and return an integer. In your answer, use either pseudo-code or C code to describe the function. (10%) (ii) In about 100 words, discuss the computational complexity and memory consumption of the iterative and recursive implementations to calculate Sand indicate which of the two implementations is preferable in this case. (10%) (iv) Write a third function that calculates in constant time, i.e. with computational complexity 0(1), the number in the series for a given index n. The function should again take an integer n as input and return an integer. In your answer, use either pseudo-code or C code to describe the function. [10%] (a) Big-Oh notation provides a way to characterise the computational complexity of an algorithm (0) () In about 100 words, explain how you could estimate the computational complexity of an algorithm (i.e. its order expressed using Big-Oh notation) by analysing its pseudo-code description, without actually running the algorithm on a computer (10%) Imagine that you are now provided an executable file that implements an algorithm whose computational complexity needs to be characterised, but you do not have access to the source code. In about 100 words, explain how you could estimate the computational complexity of an algorithm by running the executable file. (10%) (b) Consider a mathematical series such that the numbers, with index n (with n 20) is defined as follows: Su = 2 = 1 +2 +2+ + 2 + -- +2* The sequence of numbers in this series is therefore 1,3,7, 15, 31, 63, 127,- (1) Using iteration as the principal methodology, write a function that calculates the number S, in the series for a given index n. The function should take an integer n as input and return an integer. In your answer, use either pseudo- code or C code to describe the function. (10%) (1) Write a second function that calculates the numbers in the series for a given index n using recursion this time. The function should again take an integern as input and return an integer. In your answer, use either pseudo-code or C code to describe the function. (10%) (ii) In about 100 words, discuss the computational complexity and memory consumption of the iterative and recursive implementations to calculate Sand indicate which of the two implementations is preferable in this case. (10%) (iv) Write a third function that calculates in constant time, ie with computational complexity 0(1), the number S, in the series for a given index n. The function should again take an integer n as input and return an integer. In your answer, use either pseudo-code or C code to describe the function. (10%)