Linked Questions

3
votes
2answers
114 views

Is it possible to write a program that calculates an algorithm's time complexity? [duplicate]

Title is self explanatory. I have searched here on this site and haven't found any discussion about this. Is it somehow related to Turing's Halting problem (which is undecidable)?
29
votes
8answers
7k views

Is it a problem to be a programmer with no knowledge about computational complexity?

I've been assigned an exercise in my university. I took it home and tried to program an algorithm to solve it, it was something related to graphs, finding connected components, I guess. Then I made ...
3
votes
2answers
3k views

Using software to calculate the complexity of an algorithm

I am somewhat a beginner, and I have often seen complexity being calculated for various algorithms but they never actually gave me a very clear idea about how it is done. Can someone please point some ...
11
votes
3answers
507 views

Is it possible to decide if a given algorithm is asymptotically optimal?

Is there an algorithm for the following problem: Given a Turing machine $M_1$ that decides a language $L$, Is there a Turing machine $M_2$ deciding $L$ such that $t_2(n) = o(t_1(n))$? The ...
1
vote
2answers
828 views

How does the automatic complexity analysis of Codility work?

When completing exercises on Codility.com you submit your code to a server for analysis. You then receive a report containing the detected algorithm complexity of the code. I was just wondering how ...
3
votes
2answers
109 views

what is the time complexity for an algorithm that operations to complete grows by 4 when doubling the input length?

I'm working on an algorithm and I'm trying to figure out its time complexity given the operations it takes to complete a input set of specific length, I have been testing the algorithm with varying ...
2
votes
0answers
168 views

How does one heuristically determine if an algorithm has an exponential time complexity?

How does one easily determine if an algorithm has an exponential time complexity? The Word Break naive solution is known to have a time complexity of O(2n) but most people think its O(n!) because of ...
0
votes
1answer
96 views

How to express time complexity when the exponential “e” comes into play? [duplicate]

I am new to all of this and I am trying to understand how to define Time Complexity. I have an algorithm which performs a set of operations on inputs of different size. While timing the execution of ...
1
vote
1answer
45 views

Getting O-bounds by applying regression methods to execution time measurements

Does anyone of you know how to associate an algorithm execution time (of experimental execution) to a well known complexity time? For example, say a divide and conquer algorithm lasts theoretically O(...
1
vote
1answer
66 views

Why does $O(n \log n)$ seem so linear?

I've implemented an algorithm, that when analyzed should be running with the time complexity of $O(n \log n)$. However when plotting the computational time against the cardinality of the input set, ...