Question: Consider the following function which takes as input an array A of size n. For this problem use the unit cost model as a function

Consider the following function which takes as input an array A of size n. For this problem use the unit cost model as a function of n and d (assume n = 3^k ).

function mystery (A) // Assume A is an array of size n

(B, C, D) =divide(A) // divide takes time n^d

b = mystery(B) // B is of size floored[A/3]

c = mystery(C) // C is of size floored[A/3]

d = mystery(D) // D is of size floored[A/3]

return b + c + d // takes (1) time

Give a recurrence formula describing the running time

Draw the recursion tree showing level 0, level 1, level 2, level i, and level log3 n

How many subproblems are at level i of the recursion tree?

What is the cost of a single problem at level i of the recursion tree?

What is the total cost of level i of the recursion tree?

How many levels are in the recursion tree?

Write the total cost as a sum of the levels.

Simplify the sum of the total cost. Show your steps.

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

For C ( . c ) , In this assignment you'll write a program that encrypts the alphabetic letters in a file using the Hill cipher where the Hill matrix can be any size from 2 x 2 up to 9 x 9 . Your...

PROGRAM CAN BE WRITE IN C OR JAVA In this assignment you'll write a program that encrypts the alphabetic letters in a file using the Hill cipher where the Hill matrix can be any size from 2 x 2 up to...

In this assignment you'll write a program that encrypts the alphabetic letters in a file using the Hill cipher where the Hill matrix can be any size from 2 x 2 up to 9 x 9. Your program will take two...

In this assignment you'll write a program in C or java that encrypts the alphabetic letters in a file using the Hill cipher where the Hill matrix can be any size from 2 x 2 up to 9 x 9. Your program...

Please complete in C or Java not C++. write a program that encrypts the alphabetic letters in a file using the Hill cipher where the Hill matrix can be any size from 2 x 2 up to 9 x 9. Your program...

C PROGRAM In this assignment you'll write a program that encrypts the alphabetic letters in a file using the Hill cipher where the Hill matrix can be any size from 2 x 2 up to 9 x 9. Your program...

Objectives 1. Give students additional practice with functions 2. Give students additional practice with sorting structs 3. Give students additional practice with file 10 4. Give students practice...

in c++ #include using namespace std; const int arrayLength = 1000; void noCuts(int array[], int size, int cuts); int main() { int array[arrayLength]; int n = 0; cin>>n; noCuts(array, 1000, n); for...

PROGRAMMING IN C; PROPERLY - The code that was submitted to here had over 15 errors and couldnt compile whatsoever In this assignment youll write a program that encrypts the alphabetic letters in a...

Suppose a representative consumer has preference over consumption (c) and leisure (1). His indif- ference curve is described by the following function: u(c, 1) = 3 In(c) + 2 ln(1). His endowment over...

Brad, finance manager of "Auto One" is making a 12-month business plan. Assumptions: # of days = 360; Total Inventory Units = 10,000 Inventory Purchase Cost (order quantity: 10,000) = $9.50 per unit...

7 A company has recorded its unpaid bill for supplies under a current liabilities account on the balance sheet. This payment will be due to the supplier in less than a year. 1 0 - 2 4 . 5 1 True or...

8) In Raiders of the Lost Ark, Indiana Jones tried to remove a gold idol from a booby-trapped pedestal. He replaces the idol with a bag of sand. If the idol has a mass of 198lbs, how many liters of...

Within the White-Collar Occupations, where do Females have the strongest and weakest representations in the Federal Service?

What are the Five Phases of SDLC? Explain each briefly.

How can Change Control Procedures manage Project Creep?