tawhidmonowar's blog

By tawhidmonowar, 22 months ago, In English

Experimental time complexity analysis is a way to estimate the time complexity of an algorithm by running it on various inputs and measuring the running time. Here is an example of how to perform experimental time complexity analysis in C++:

#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;

void someAlgorithm(int n) {
  // code for the algorithm
}

int main() {
  int n;
  cin >> n;

  auto start = high_resolution_clock::now();
  someAlgorithm(n);
  auto stop = high_resolution_clock::now();
  auto duration = duration_cast<microseconds>(stop - start);

  cout << "Time taken by function: "
       << duration.count() << " microseconds" << endl;
  return 0;
}

In this example, we have a function someAlgorithm() that takes an input parameter n. We use the library to measure the running time of the function by recording the start time and end time using high_resolution_clock::now(), and then calculating the duration using duration_cast(stop — start).

To perform the experimental time complexity analysis, we can run the someAlgorithm() function with various input sizes (for example, 10, 100, 1000, 10000, etc.), and record the corresponding running times. We can then plot the running times against the input sizes on a graph, and try to fit a curve to the data. The shape of the curve can give us an idea of the time complexity of the algorithm. For example, if the curve looks linear, then the algorithm is likely to have linear time complexity. If the curve looks quadratic, then the algorithm is likely to have quadratic time complexity.

However, it is important to note that experimental time complexity analysis is not a rigorous method and should be used with caution.

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey That was really helpful however when I tried to run this code there seems to be some kind of syntax error like

auto duration = duration_cast<microseconds>(stop &mdash; start);

The problem was with this line and when I changed this to the line below it seems to work for me

auto duration = duration_cast<microseconds>(stop - start);