lab2

Please write the analysis/reflection to a wiki page in your repo called lab2

Perform a full analysis of both the power() and factorial() function (but NOT fibonacci()). That is for these two functions, find T(n) which represents the worst case complexity for these two functions. State their upper bounds. Please see https://catherine-leung.gitbook.io/data-strutures-and-algorithms/recursion/analysis-of-a-recursive-function on how to do a recursive analysis.

Main idea of recursion is to split problem(rec case) until it cant be splitter no more (base case)

factorial: we skip insignificant operations and are left with rec case that matters //
T(1) or T(0) = 3, since its never hits rec case and execute base case.
T(n) = 6+T(n−1) where 6 is minimum of 6 times for 2 base cases that are not hit right away (n != 0 and n!= 1) thus we go with recursive case after T(n−1), next we have T(n) = 6n−3 . which is O(n) - linear complexity Power: T(0) = 3, next we go with rec func for T(n)m following same logic T(n) = 2n, which is O(n) - linear complexity

Answer the following questions regarding the fibonacci() function (You do NOT need do an analysis of fibonacci()): Did you find it easier to write the recursive fibonacii() function or the iterative version? Without performing a full analysis

At first it was easier to write linear, but recursive approach is a bit more good looking and performs better, because even the our T(n) is o(n2) recursive version goes twice as fast, because diving in 2 (n/2) , it will be faster.


there is no right or wrong to this question ... just give it your honest best guess. Its a hypothesis... don't google for the answer. This is a hypothesis. You do this then see if your observations support what you think. Its ok to be wrong. what do you think the runtime of your recursive fibonacci function is (stated with big-O notation)? Explain why you think this.

Modify the file lab2timing.cpp to get a timing of running the fibonacci function. Record the time needed to run fib for n ranging from 21 to 45 inclusive (timing results for values smaller than 21 are pretty small but feel free to run and include them if you want). Feel free to modify lab2timing.cpp however you want to get the data you need.

Given the timing, and your original guess, does the run time fit your original hypothesis?

Actually yes and no, but on the screen graph seems like it is log, if we had negative numbers it club actually also be squared graph but it is not possible ) I failed to see that computation is actually logn and not n2 like in case of linear, so endeed rec way is after and I was right, its because comp complexity is log for recursive way.

Given the timing, and your original guess, does the run time fit your original hypothesis?

As I explained , not really)) but it was a good try )