文档介绍：(a) is true; (b) i s true; (c) is fal se (example: T1( N ) = N and
T2( N ) = 1 ); (d) is false (same example).
running time is O( N ), assuming that each multiplication is unit cost.
This assumption is somewhat unjustified since it is clear that the numbers
are getting bigger at each step. But at this level, deeper calculations are
not needed. If we take the size of X as a constant, then the ith multiplica-
tion costs O( i ), and theNtotal running time is quadratic
analysis below will agree with the simulation in all cases. Fragment 1
and 2: The running time is O( N ). Fragment 3: The running time is
O( N 2 ) because of two nested loops of size N each. Fragment 4: The
loops are consecutive, so the running time is O( N ). Fragment 5: The
inner loop is of size N 2 so the running time is O( N 3 ). Fragment 6: The
running time is O( N 2 ). Fragment 7: Here we have three nested loops of
size N, N 2 , and N 2 , respectively, so the total running time is O( N 5 )
the if statement is executed at most N 3 times, but it is only true
O( N 2 ) times (because it is true exactly i times for each i). Thus the
innermost loop is only executed O( N 2 ) times. Each time through it takes
O( N 2 ) time, for a total of O( N 4 ).
the first case, the %p is missing (see what happens when N is a power
of 2). Even if the %p is placed at the end of the l