本次澳洲代写是一个Java/C++算法的assignment

IMPORTANT NOTES (PLEASE READ BEFORE WORKING ON THE SOLUTION):

• Please read the entire of this question sheet before starting to work on the solution.
• Your assignment should consist of a single .pdf, named A2-[studentID].pdf and a single .cpp/.java file, named
  A2-[studentID].cpp or A2-[studentID].java. You should zip these two files together into a single file, named the
  .zip file A2-[studentID].zip and submit via Wattle before the due date.
• We provide 13 hours grace period. This means, there will be no penalty if you submit before the grace period
  ends. However, we will NOT accept assignment submission beyond this time (i.e., late penalty after the grace
  period ends is 100%).
  – You can update your assignment until the grace period ends.
• Assignment marking:
• – The total mark you can get in this assignment is 100 points.
  – This assignment will contribute 20% to your overall mark.
  – In each question, you need to provide a convincing argument (including mathematical derivation) that
  supports your answer. The argument is worth 80% of the marks, while the solution alone is 20%.
• Discussion with your colleagues are allowed and encouraged. However, you need to work on the assignment
  on your own AND write the names you discussed this assignment with.

In all the questions below, you can assume that all n are positive integers.

[30 pts] Part A

1. [10 pt] Given the following recurrence, please answer the questions below

where c is a positive constant.

(a) [2.5 pt] Can Master Theorem be used to solve this recurrence?
(b) [7.5 pt] Please find a tight asymptotic bound (i.e., ) to the solution of the above recurrence.