Posted by hussein on August 06, 2000 at 15:53:32:
In Reply to: an alg analysis question posted by sabrina on August 06, 2000 at 12:22:47:
to answer your questions in order:
yes, i<n-1 will execute n times because each time an increment and check is done, and one check is also done before the first iteration (this means that the notes are wrong by a fixed value of 1 - why is this generally not important?)
and, yes, i++ will execute n-1 times since it occurs once after every iteration
also, yes, since the outer loop executes (n-1) times, the inner condition will be evaluated (n-1) more than the increment (j++) when you sum over all iterations of the inner loop ...
then the total time will definitely be different (by n) from whats in the notes.
the corrected sum should be T(n)=3+sum^{n-1}_{i=1} (5+sum^{i}_{j=1} 3)
(where sum^{b}_{c} means the summation from c to b)