Consider the following recurrence, defined for n a power of 4 (for the time of some algorithm): T(n) = 3 if n = 1 2T(n/4) + 4n +
1 otherwise (a) Calculate T(16) by hand. Show your work. (b) Use the tree method to solve the recurrence exactly, assuming n is a power of 4. (c) Use the formula to calculate T(1). Show your work. (d) Use the formula to calculate T(4). Show your work. (e) Use the formula to calculate T(16). Show your work. (f) Use Mathematical Induction to prove that your formula is correct in general.
1 answer:
You might be interested in
Following are the python program to the given question:
from collections import defaultdict #import package
import heapq as h#import package
def primsMST(gr, st_v): # defining a method primsMST that takes two values in parameters
primalMST = defaultdict(set)#defining primalMST as a variable that calls defaultdict method
v = set([st_v])# defining a variable v that calls the set method and hold its value
e_list = [(c, st_v, to)for to, c in gr[st_v].items()]#defining variable e_list that use loop to hold value in list
h.heapify(e_list)# use package that holds heapify and holds its value
while e_list:#defining while loop that checks e_list
c, s, e = h.heappop(e_list)#holding heapop method value in c,s,and e variable
if e not in v:#defining if block checks e value is not in v
v.add(e)# use add method to add value in v
primalMST[s].add(e)#use primalMST as list that adds value in mwthod
for nxt, c in gr[e].items():#defining for loop that uses nxt, and c variable that checks value in list
if nxt not in v:#defining nxt variable that checks value is not in v
h.heappush(e_list, (c, e, nxt))#add value into the heappush method
return primalMST#return method value
connects=[['A','B',1],['B','C',4],['B','D',6],['D','E',5],['C','E',1]]#defining a list connects
my_gr=dict()#defining a variable my_gr that holds method dict() value
for el in connects:#defining a for loop that uses el to count connects list value
my_gr[el[0]]=dict()#use my_gr as list hold value in dict method
my_gr[el[1]]=dict()#use my_gr as list hold value in dict method
for el in connects:#defining another for loop that uses el to count connects list
my_gr[el[0]].update({el[1]:el[2]}) # use update method that update value in my_gr
my_gr[el[1]].update({el[0]:el[2]})# use update method that update value in my_gr
x=dict(primsMST(my_gr, list(my_gr.keys())[0]))#defining x variable that calls dict method and hold its value
a=[]#defining an empty list
for k in x:#defining a for loop that uses k to hold dict method value
for no in x[k]:#defining a loop that checks list value
a.append([k,no,my_gr[k][no]])#use a that add value in list
print(a)#print list value.
Output:
Please find the attached file.
Program Explanation:
- Import package.
- defining a method primsMST that takes "gr and st_v" as parameters.
- Inside the method, a primalMST as a variable is declared that calls "defaultdict" method.
- Use the v variable that calls the set method and hold its value.
- Defining "e_list" that uses the loop to hold value in lists, and define the heapify and holds its value.
- In the next step, it defines a while loop checks e_list, and defines variable and hold value into the method and use another if to check value and return its value.
- A list "connects" is declared that holds a value and defines a "my_gr" that holds "dict" method value and uses multiple for loop to print the calculated list value.
Learn more:
dictionary: brainly.in/question/14673591
List: brainly.in/question/25140412
