I have studied complexity of algorithms that how long an algorithm will take to execute completely, then why it is said that certain programming languages are faster than others such as C++ is faster than python.
Add a comment |
1 Answer
First of all, programming language can have an effect on the time complexity of algorithms. For example, many algorithms rely on mutating an element in an array in O(1) time. So any language that doesn't have mutable arrays (and it's not hard to imagine e.g. a dialect of Haskell that doesn't have them) will have worse time complexity for many algorithms.
But that's not the case here. While there are many differences between C++ and Python, their core capabilities are similar enough that for any algorithm you can write in one of them, you can also write it in the other one, with the same time complexity.
But time complexity is not the same thing as performance. If I know that the complexity of some algorithm is O(1), I still don't know how long executing an implementation of that algorithm for some input will actually take: it could be 1 nanosecond, 100 years, or anything in between. And because of the way the two languages are designed and implemented, a program in C++ will almost always have better performance than an equivalent program in Python. Which is why it's said that C++ is faster than Python.
- "For example, many algorithms rely on mutating an element in an array in O(1) time.": To be pedantic, for each such algorithm there could exist another algorithm that performs the same task, does not need mutation, and still has the same or better complexity. So, yes, you cannot implement the same algorithm efficiently without mutation, but there could be an efficient solution to the same problem that does not require mutation.– GiorgioCommentedMay 2, 2019 at 9:48
- 1@Giorgio The question specifically asked about the complexity of algorithms, not complexity of problems, so I think my answer still stands.– svickCommentedMay 2, 2019 at 20:49
