CODEWITHSUNDEEP
algorithmgraphbig-otime-complexity
Travelling Salesman
Travelling Salesman

Reputation: 2271

Time Complexity and Experimental Results

I have two algorithms A and B, that work on Logical Graphs, and I would like to compare their efficiency in term of time.

When I calculated the time complexity for both algorithms I found:

Time Complexity of A: O(2*n*n)
Time Complexity of B: O((n*n)/2)

According to Wikipedia, http://en.wikipedia.org/wiki/Time_complexity we ignore the coefficients when we calculate the time complexity, which yields:

Time Complexity of A: O(n^2)
Time Complexity of B: O(n^2)

The second step I did is to experimentally calculate the time that each algorithm takes for different sizes of graphs. Below, x axis represents the number of nodes in the graph, y axis is the time in seconds.

Time Comparison Between A and B. x is number of nodes, y is time in seconds

As you can see, there is a large difference between the two algorithms for large graphs. My Question is: Is this reasonable? Is it possible to have two algorithms with the same time complexity but with this large difference in time when it comes to practice? Thank you.

Upvotes: 3

Views: 1700

Answers (1)

user529758
user529758

Reputation:

Yes, it's absolutely reasonable. Computational complexity doesn't show how fast an algorithm exactly is - it rather shows how it reacts to changes in the size of the input.

It's not a coincidence asymptotic complexity is called asymptotic and not "identical".

Upvotes: 3

Related Questions