Analysis of Algorithm - Part 1 of 3: recursive definition Given the following function f, written in pseudocode similar to C or Java: void f( int n){ if (n=0) print("hello") else if (n==1) print ("hellohello") else \{ f(n2) print("hellohellohello") f(n2) \} Define the sequence hn= the number of hellos printed by f(n). Give a recursive definition of hn. This definition must include: - All the initial conditions needed to define this sequence (do not give more or fewer than needed) - A recurrence relation as a function of some of the elements of the sequence that precede hn - The values of n for which this recurrence relation applies Explain this recursive definition. This explanation must include: - an explanation of the recurrence relation - an explanation of how you decided how many initial conditions were needed for this recursive definition Note that the explanations are the most important part of this question. Do not simply give answers fo your mathematical formulas. Explain your reasoning! You may find it useful to begin working on the next question at the same time as this question particularly if you are finding this question challenging. Analysis of Algorithm - Part 2 of 3: first 10 terms In the remaining questions you will use iteration to deduce an analytical solution for this sequence: In this question, please write out the first 10 terms (from 0 to 9 ) of the sequence hn. Show and keep the intermediate expansions because they will turn out to be more important than the final values for noticing a pattern (and your grade will depend on it). In other words: Do distribute your operations to remove the parentheses in each term of the sequence, but be very careful when calculating the results of additions, multiplications, and exponentiations, because the pattern will disappear if you go too far. + Drag and drop an image or PDF file or click to browse... Q2-pg3 (10 points) Analysis of Algorithm - Part 3 of 3: Analytical solution You will now find an analytical solution for hn. Your final formulas should not include any or operators. To find an analytical solution for hn, it is useful to break down the work into two parts: 1 - Based on the first 10 terms of hn, guess non-recursive formulas for the even and odd terms of the sequence, i.e. one formula for hn when n is even and another formula when n is odd. Hint: somewhere along the way, your two formulas will probably include a well known series or product that you Analysis of Algorithm - Part 3 of 3: Analytical solution You will now find an analytical solution for hn. Your final formulas should not include any or operators. To find an analytical solution for hn, it is useful to break down the work into two parts: 1 - Based on the first 10 terms of hn, guess non-recursive formulas for the even and odd terms of the sequence, i.e. one formula for hn when n is even and another formula when n is odd. Hint: somewhere along the way, your two formulas will probably include a well known series or product that you can solve. You may have already done this in the previous page, but if not, now is the time. Remember, iteration is a slow process where the journey usually reveals more information than the destination. This is definitely the case with this problem. If you do not see patterns in your answers, it is probably because you skipped some intermediate steps. Go back to the previous page, and slow down 2 - Give a single analytical solution for hn, i.e. a single formula that will work for all values of n starting at 0 . In this part, you will need to figure out how to merge the even and odd cases into a single mathematical formula. This can usually be accomplished by using some of the mod, floor and ceiling operators. Before you attempt to do so, be sure that your two separate formulas are correct by checking them against the values for h0 to h9 that you calculated in the previous page