// Print n-Fibonacci number
// 3 variants of realization

#include <iostream>
#include <vector>
#include <exception>
#include <chrono>
#include <ctime>

using namespace std;

// O(2^n)
// The worst realization, too long:
int GetFiboExponential(int n) {
  if (n < 2)
    return n;
  return GetFiboExponential(n - 1) + GetFiboExponential(n - 2);
}

// O(n)
// Ok but additional O(n) memory used:
int GetFiboLinear(int n) {
  if (n < 2)
    return n;
  vector<int> result(n + 1, 0);
  for (int i = 0; i <= n; ++i)
    if (i < 2)
      result[i] = i;
    else
      result[i] = result[i-1] + result[i-2];
  return result.back();
}

// O(n)
// Good, no additional memory:
int GetFibo(int n) {
  int n_2 = 0;
  int n_1 = 1;
  int f = n;
  for (int i = 1; i < n; ++i) {
    f = n_2 + n_1;
    n_2 = n_1;
    n_1 = f;
  }
  return f;
}

template <typename FuncType>
void CountTimeOfFibo(FuncType func, int n) {
  clock_t start = clock();
  cout << "\t" << func(n);
  cout << ", time = ";
  cout << chrono::duration<double, std::milli>(clock() - start).count();
  cout << " ms" << endl;
}

void check(int n) {
  if (n < 0)
    throw std::runtime_error("Invalid input data");
}

int main() {
  while (true) {
    cout << "Enter number: ";
    int n;
    cin >> n;
    check(n);
    cout << "Fibonacci number is:" << endl;
    CountTimeOfFibo(GetFiboExponential, n);
    CountTimeOfFibo(GetFiboLinear, n);
    CountTimeOfFibo(GetFibo, n);
  }
  return 0;
}