Answered: Profile the performance of the memoized…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Profile the performance of the memoized version of the Fibonacci function defined in Project 6. The function should count the number of recursive calls. State its computational complexity using big-O notation, and justify your answer.

The fib function header has been modified to include the counter as the second parameter.

Define the Counter class, it should have three methods: __init__, increment, and __str__. When an instance of the Counter class is passed as a parameter, the count property of that instance should be incremented based on the number of recursive calls. The __str__ method should return the count property's value as a string.

-----------------------------------------------------------------------------------

"""

File: fib.py

Project 11.7

Employs memoization to improve the efficiency of recursive Fibonacci.

Counts the calls and displays the results.

"""

class Counter(object):

"""Tracks a count."""

# Define the Counter class here.

def fib(n, counter = None):

"""Fibonacci function with a table for memoization."""

table = {}

def memoizedFib(n):

if n < 3:

return 1

else:

# Attempt to get value for memoizedFib(n)

# from the table

# If unsuccessful, recurse and add results to

# the table

value = table.get(n, None)

if value: return value

else:

value = memoizedFib(n - 1) + memoizedFib(n - 2)

table[n] = value

return value

return memoizedFib(n)

def main():

"""Tests the function with some powers of 2."""

problemSize = 2

print("%4s%12s" % ("n", "fib(n)"))

for count in range(5):

print("%4d%12d" % (problemSize, fib(problemSize)))

problemSize *= 2

if __name__ == "__main__":

main()

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions