URGENT 

I need help with this computer science question. All tutors so far have answered it wrong. I have attached the pdf with the description - please help me!! The answers are only supposed to be mathematical equations, no java code. 

 

Question 2(40 points)a) (10 points)Solve the recurrence࠵(±) = ࠵ ²³2´ + µ¶·2±,such that࠵(1) = 0.Assume in your solution that±is a power of 2,that is,± =¸¹so¹ = µ¶·2± .b) (10 points)Verify that your answer in (a) is correct using a proof by mathematical induction, namely performinduction on the variable¹.c) (10 points)If two positive integers±ºand±2have»ºand»2decimal digits, respectively, then computingtheir product±º*±2using the grade school multiplication algorithm has time complexity¼(»1»¸).Question:For a given positive integer±,what is the¼( )time complexity of computing±³,that is,±to the power±?Hints:xThe answer is not¼( »±),i.e.¼( (µ¶·10±)½).Such an answer would ignore the fact(s)that you need multiply±repeatedly by itself, and that the result has an increasing number ofdigits.xAnswer this question using arguments and concepts that were covered prior to lecture 14.i.e.Do not use the lecture 14 formal definition of big O here.xIn answering the question, donotattempt to use any tricks such as computing±8by firstcomputing±4and then squaring the result.In fact, such tricks do not speed up thecomputation of±³in a big O sense.I will discuss this later in the course, time permitting.xThe number of digits»to represent a positive integer±in base 10 is floor(µ¶·º¾±) + 1,but toanswer the question, you should approximate this formula asµ¶·º¾±.See lecture notes 2pages 5,6 where a similar formula is derived for base 2.

• 1495088107-A2Q2.pdf

SuperTutor

(15)

Status NEW Posted 18 May 2017 06:05 AM My Price 9.00

-----------

Attachments

file 1495088109-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer