6 ms·
That's not even close to all there is to it. Complexity analysis is a relatively young field with lots of deceptively simple unsolved problems. For a simple ex
by creata 6y ago
That's not even close to all there is to it. Complexity analysis is a relatively young field with lots of deceptively simple unsolved problems.
For a simple example of how it's a lot more than that, follow Tarjan's proof of the disjoint set's amortized time complexity[0]. It's not at all obvious, even though the disjoint set is a very simple and practical data structure.
[0]: http://www.e-maxx.ru/bookz/files/dsu/Efficiency%20of%20a%20Good%20But%20Not%20Linear%20Set%20Union%20Algorithm.%20Tarjan.pdf http://www.e-maxx.ru/bookz/files/dsu/Efficiency%20of%20a%20G...
- andi999 6y agoSo what would be a deceptivly simple unsolved problem?
- creata 6y agoWikipedia has a list of big-name unsolved problems in complexity theory. Most of these have very simple problem statements. https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science#Computational_complexity https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_c...
- adamnemecek 6y agoP == NP on analog quantum computers. A light prism performs a diagonalization which can be used to do factorization in O(1).
- rytill 6y agoFactorization of arbitrarily large numbers? I doubt it.
- adamnemecek 6y agoYes.
- amelius 6y agoOn constant-size hardware? And doesn't getting the data in and out already take O(N)?
- adamnemecek 6y agoAre you talking about arbitrary sized or infinite sized?
- rytill 6y agoWe’re saying the time, space, or some other metric of the solution scales with the size of the input number in a way that is not constant. The number could be any input (arbitrary).