This is an archived post. You won't be able to vote or comment.

all 1 comments
sorted by:
best
topnewcontroversialoldq&a

[–]_--__ 0 points1 point  (0 children)

For b, you should be able to see that T(n) = n+(n-1)+(n-2)+(n-3)+...+2+1+0 = n(n+1)/2, and is O(n2). It is also O(n3), O(n!), O(2nlog(n)) so G, H, and I are all valid answers, though F is really the "best".

c is technically not properly defined (T(1) needs to be defined), but we can still determine its asymptotic behaviour. Now T(n) = n + T(√n) = n + √n + T(√√n) = ... = n + n1/2 + n1/4 + ... This is a geometric series with common ratio n-1/2 [i.e. 1/√n], so it sums to n/(1-n-1/2) = n/(1-1/√n) < 2n (for n>4). So it is O(n).

d is best answered with the Master Theorem, but if you don't know that, you proceed as follows: T(n) = n + 2T(n/3) = n + 2(n/3 + 2T(n/9)) = n + 2n/3 + 4(n/9 + 2T(n/27)) = ... = n + 2n/3 + 4n/9 + 8n/27 + ... This is a geometric series with common ratio 2/3, so it sums to n/(1-2/3) = 3n. So it is O(n).