Timeline for Big-O for nested loop
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 2, 2011 at 9:20 | vote | accept | user10326 | ||
| Sep 30, 2011 at 17:59 | comment | added | Newtopian | @Donal : probably not no :-) | |
| Sep 30, 2011 at 12:34 | comment | added | Donal Fellows | @Newtopian: To be fair, the ContainsDuplicates function/method from the question isn't very likely to be used with full chromosomes. | |
| Sep 27, 2011 at 3:36 | comment | added | Newtopian | @Donal indeed, we can, with proper data set knowledge make such assumptions, but as always there are exceptions, DNA analysis comes to mind where string length can be a few characters in length for a codon to multi mega bytes for a full chromosome. That said in this case in particular example the string length is of no consequence since we iterate the strings themselves, not the characters. That is, unless the equality operator has been overloaded to some funky logic depending on length of the operands. I doubt however the OP intended to dig this far in his analysis. | |
| Sep 26, 2011 at 13:10 | comment | added | Donal Fellows | @Newtopian: You usually assume that the strings are about constant in length; that's actually a pretty good approximation in practice. | |
| Sep 26, 2011 at 2:53 | history | edited | Jon Purdy | CC BY-SA 3.0 | Improved formatting. |
| Sep 26, 2011 at 2:20 | comment | added | Newtopian | perhaps an easier to understand notation would be to say that the algorithm runs in O(i*j). Here both loops iterate over the length f String, thus i = j = n where n is strings.length | |
| Sep 25, 2011 at 21:26 | history | answered | KeithB | CC BY-SA 3.0 |