3 ms·
Count the number of nested loops. If one of the loops does splitting (like binary search) it’s a O(log n) as opposed to O(n). That’s literally all there is to
by adamnemecek 6y ago
Count the number of nested loops. If one of the loops does splitting (like binary search) it’s a O(log n) as opposed to O(n).
That’s literally all there is to it.
- jkaptur 6y agoWhat if there are recursive function calls?
- pmiller2 6y agoThen you get to have fun solving a recurrence relation. :-)
- johndough 6y agoIf you don't like "fun", WolframAlpha can solve those for you. :-) https://www.wolframalpha.com/input/?i=f%281%29+%3D+1%2C+f%282%29+%3D+1%2C+f%28n%29+%3D+f%28n+-+1%29+%2B+f%28n+-+2%29 https://www.wolframalpha.com/input/?i=f%281%29+%3D+1%2C+f%28...
- pmiller2 6y agoSure, but if you're not on the spot in an interview, the master theorem is simple enough to apply: https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Generic_form https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_al...
- commandnotfound 6y agoThank you, but for the link provided it only says that these are the Fibonacci numbers and nothing more. Yes, you can click on this F(n) (how can you even know this is a link), but anyways.
- miguelrochefort 6y agobranchesᵈᵉᵖᵗʰ
- nkozyra 6y agoThat covers most of the algorithms you'll see in a coding interview test, but there's a ton more complexities outside of search spaces, sorts and nested O(n) loops. Even some graph operations will leave familiar territory.
- creata 6y agoThat'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.
- dragontamer 6y agoStrassen algorithm is 7-multiplications for a 2x2 matrix. https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm A matrix can always be split into groups of sub-matrix, and the groups of sub-matrix is itself a matrix. Applying Strassen algorithm recursively is therefore O(n^log2(7)) == O(n^2.8ish).
- adamnemecek 6y agoThe article covers none of those.