147 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)?
8k 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 ...
5k 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 ...
584 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 ...
1k 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 ...
111 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 ...
191 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, ...
189 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 ...