Reference no: EM132494001

Design an algorithm using the greedy pattern for Uphill problem: Input: a vector V of n positive integers

Output: an index i, such that the element V[i] is equal to the sum of all elements before V[i] which are V[0], V[1]..., V[i-1]; or None if no such index exists

Example: for input V=[3, 2, 5, 1, 3, 1], output is i=2 because V[i]=V[2]=5 and (3+2)==5. For input [] (empty vector) or V=[1, 1, 1, 2], the output is None.

Write the pseudocode of your algorithm. If you write multiple drafts, circle your final draft. Hint: I expect your algorithm to be relatively simple and to have time complexity O(n^2) .

Calculate the step count T(n) of your algorithm. Show your work.