Hi,
I guess your reasoning is correct. I only have a few remarks:
+ Algorithm 1: "from 0 to N is used" --> "from 1 to N are used"
+ Analysis of Algorithm 1: I think you are right in concluding that it's "O(infinity)". My hunch is that your instructor should have mentioned that the sequence a a a a ... a (ad infinitum) cannot arise, even though this sequence is as random as any other. If you may assume this, then O(N^2) holds but only under the additional assumption that O(randInt(...)) is O(1).
This discussion reminds me of Donald Knuth's recent remark that big-oh notation is often used incorrectly, also by a large part of the academic community. See chapter 3 in Knuth's latest book:
+ Knuth, Daylight, "Algorithmic Barriers Falling: P = NP?", Lonely Scholar, November 2014: www.lonelyscholar.com
best wishes,
Alicia
