Linked Questions

4 votes
2 answers

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)?
ihavenoidea's user avatar
30 votes
8 answers

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 ...
Red Banana's user avatar
3 votes
2 answers

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 ...
Pankaj Sejwal's user avatar
11 votes
3 answers

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 ...
StaticBug's user avatar
  • 213
1 vote
2 answers

How does the automatic complexity analysis of Codility work?

When completing exercises on 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 ...
js837's user avatar
  • 13
1 vote
1 answer

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, ...
Andreas V.'s user avatar
3 votes
2 answers

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 ...
Jesus Salas's user avatar
0 votes
1 answer

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 ...
FaCoffee's user avatar
  • 123
2 votes
0 answers

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 ...
perseverance's user avatar
1 vote
1 answer

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(...
dunnomuch's user avatar