I'm trying to code something that's a little complex, imo.
It's a C++ program that will count the number of operations of recursive functions and will compare it with O(g(n)). This count value will basically estimate time complexity function T(n). You have to find the g(n) to get O(g(n)) that acts as upper bound. The program takes as input n, some positive integer and choosing between a recursive or non-recursive version, It's gonna evaluate two recursive functions:
fibonacci(n)=fibonacci(n-1)+fibonacci(n-2); starting at fibonacci(1)=1 and fibonacci(2)=1
The code will have to produce one line of output per function at some n value showing:
result, operation count (T(n)) and worst-case time complexity with your estimated O(g(n)) exhibiting c and some n0, according to the definition (n0 greater or equal than 2). It must find some c value so that the inequality always
holds (the tigther the better).
And the output - it needs produce n rows with 7 columns, varying n from 1 to the n value given as parameter.
In each row values are separated with spaces. The first column is n and then there are three columns per recursive function, showing partial result, T(n) and O(g(n)). Numbers should appear right aligned.
It's gonna look like this:
I am not getting it. Can someone please tell me how to get started here? The hardest part for me here is developing the recursive and non recursive function that will calculate it.:S