Do the following tasks:

i$.$ Design and implement an efficient algorithm that computes the OSR metric for the MCM Problem's DP solution and generates the OSR metric table up to an entered table size $($See the sample output below$)(80$ pts $)$

ii$.$ Analyze your algorithm's time complexity by making comments about it$.$ There is no need for line by line analysis. $(20$ pts$)$

SAMPLE OUTPUT:

Enter table size: $10$

Reference:

$[1]$ Cormen, T$.,$ Leiserson, C$.,$ Rivest, R$.$ and Stein, C$.,$ Introduction to Algorithms $($Third Edition$),$ The MIT Press, $2009,$ ISBN: $978-0-262-03384-8$

PS:

$1.$ You are required to work either alone or in at most three$-$person groups.

$2.$ If you wish to work as a group, all the group members should send an e$-$mail $($furkan$.$bakal@atilim.edu.tr$)$ indicating the name of his$/$her agreed group member until $08\mathrm{.}12\mathrm{.}2024($Sunday$)$ Hr:$23$:$59.$ Otherwise, it is assumed that you will work alone $($by default$).$

$3.$ Note that besides submitting the homework, you are also required to attend code review $\backslash$& demonstration of your code.

$4.$ Percentages of written part submission and demo parts are $\backslash (\backslash \%70\backslash )$ and $\backslash (\backslash \%30\backslash )$ of your overall Homework $\backslash$#$2$ grade, respectively. Submissions without code review $\backslash$& demonstrations gets $\backslash (\backslash$mathbf$\{0\}\backslash )($zero$)$ grade from both parts, directly.

$5.$ Time table for the code review $\backslash$& demos to be announced later via course Moodle site.

$6.$ For Part $1,$ you can prefer any one of the programming languages $\backslash (\backslash$mathbf$\{$C$\},\backslash$mathbf$\{$C$\}\_\{++\}\backslash )$or Python as your implementation language. Do NOT submit a screen shot of your source code but submit it as a text file!!!

$7.$ Your answer for Part $\backslash (\backslash$mathbf$\{2\}\backslash )$ should be submitted as a handwritten separate file.

I made this code def compute$\_$osr$\_$metric$($n$)$:

$"""$

$$ Function to compute overlapping recursive calls, total recursive calls,

$$ and the OSR metric based on matrix chain multiplication.

$"""$

$$ if n $==1$:

$$ overlapping$\_$calls $=0$

$$ total$\_$calls $=1$

$$ elif n $==2$:

$$ overlapping$\_$calls $=0$

$$ total$\_$calls $=3$

$$ else:

$$ total$\_$calls $=3**($n $-1)$# Total recursive calls

$$ overlapping$\_$calls $=$ total$\_$calls $-($n $*($n $-1))$# Overlapping calls using the provided formula

$$

$$ # OSR metric result: overlapping$\_$calls $/$ total$\_$calls

$$ osr$\_$metric $=$ overlapping$\_$calls $/$ total$\_$calls if total$\_$calls $!=0$ else $0$

$$ return overlapping$\_$calls, total$\_$calls, osr$\_$metric

def generate$\_$table$($size$)$:

$$ print$($f$"$

$\{\text{'}$Matrix Chain Size':$<mn>2</mn><mn>0</mn><mi>\}</mi><mtext></mtext><mi>\{</mi><mi>\text{'}</mi>$Total Recursive Calls':$<mn>3</mn><mn>0</mn><mi>\}</mi><mtext></mtext><mi>"</mi>$

$$ f$"\{\text{'}$Overlapping Recursive Calls':$<mn>3</mn><mn>0</mn><mi>\}</mi><mtext></mtext><mi>\{</mi><mi>\text{'}</mi>$OSR $($Overlapping Subproblem Ratio$)\text{'}$:$<mn>2</mn><mn>0</mn><mi>\}</mi><mi>"</mi><mi>)</mi>$

$$ print$("-"*100)$

$$

$$ for n in range$(1,$ size $+1)$:

$$ overlapping$\_$calls, total$\_$calls, osr$\_$metric $=$ compute$\_$osr$\_$metric$($n$)$

$$ print$($f$"\{$n:$<mn>2</mn><mn>0</mn><mi>\}</mi><mtext></mtext><mi>\{</mi>$total$\_$calls:$<mn>3</mn><mn>0</mn><mi>\}</mi><mtext></mtext><mi>\{</mi>$overlapping$\_$calls:$<mn>3</mn><mn>0</mn><mi>\}</mi><mtext></mtext><mi>\{</mi>$osr$\_$metric:$<mn>2</mn><mn>0</mn><mn>.</mn><mn>4</mn>$f$\}")$

def main$()$:

$$ print$("$OSR Metric Table Generator"$)$

$$ try:

$$ table$\_$size $=$ int$($input$("$Enter the number of matrices $($size n$)$: $"))$

$$ if table$\_$size :

$$ print$("$Please enter a positive integer for the table size."$)$

$$ return

$$ generate$\_$table$($table$\_$size$)$

$$ except ValueError:

$$ print$("$Invalid input. Please enter an integer for the table size."$)$

if $\_\_$name$\_\_=="\_\_$main$\_\_"$:

$$ main$()$

but this code is not calculate overlapping recursivce calls truely I need help for calculate them correct. I guess correct ones something like