Uploaded LList.java to github. It still needs some formatting work, as the code to exhibit the functionality (The LListTest class) should probably be in a separate document from LList
The LList class's actual behavior doesn't start until line 64, which probably isn't good.
I also finished up big O notation in eimacs and started reading about it in the Software Engineering and Development book. It seems like a thorough explanation so far, but there are still things that they don't explain. This might just be because I'm jumping into the middle of the book, though.
The main thing was that in this image, they don't really explain where they get the ~(N^2)/2 and ~(N^3)/6 from. I'm assuming it's just because you don't know when the if conditional will be satisfied, but it will average out to being near the middle, hence the 1/2.
Two comments:
ReplyDelete1. Thank you for sharing your java implementation of LList. It provides a clear reminder as to why I love Python so much ;-)
2. The /6 gets ignored in Big-O analysis, so this loop would be O(n**3), right?