Common program call sequences/sums:

- Sum of numbers:
1+2+3+4+ ...+ N=N(N−1)2≡Θ(N2) - Geometric sum:
1+2+4+8+ ...+ N=2N−1≡Θ(N) - Sum of squares:
1+4+9+16+ ...+ N2≡Θ(N3) - Sum of subarray lengths:
(N)(1)+(N−1)(2)+ ...+ (2)(N−1)+(1)(N)=Θ(N3) - Sum of logs:
log1+log2+log3+ ...+ logN=logN!≡Θ(NlogN)

- Sum of numbers:
Common methods to solving problems:

For the example program:

public static int func(int N) {if (N <= 1)return 1;return func(N - 1) + func(N - 1);}**Recursion method**: if every time we increaseN by1 the work doubles, this isΘ(2N) runtime**Recurrence method**: count the number of calls to a given function (known as a recurrence relation)- For the code above, let
C(N) be the number of calls for a givenN - Then we have
C(1)=1 andC(N)=2C(N−1)+1≡2C(N−1) - We can solve this algebraically:
- Or (usually easier/faster method) count the number of calls in a figure such as the one below to get the function call sum:
- This gives
C(N)=1+2+4+8+ ...+ 2N−1=Θ(2N)

- For the code above, let

- Binary search example:
- Solving with recurrence method, we have
C(0)=0,C(1)=1,C(N)=1+C(N−12) - This gives
C(N)=1+1+ ...+ 1+0=k (there arek many1 's in the sum because ofk many function calls) - Observing the recurrence equation shows that this
k=logN - Thus the runtime is
Θ(logN)

- Solving with recurrence method, we have
- Merge sort example:
- At top level we do
N amount of work - Then we split into two two
N/2 size groups and doN/2 work for each - Continue splitting down till group size
=1 - Thus, at each level we do a total of
N work, and we have a total ofk=logN levels - This gives a runtime of
Θ(NlogN) - Visualized in diagram below:
- Equivalently, using recurrence method,
C(1)=1,C(N)=2C(N/2)+N - This is solved below (
lg=log2 ):

- At top level we do