## Lecture 18 - 03/01

### Asymptotics 2

• Common program call sequences/sums:

• Sum of numbers: 1+2+3+4+ ...+ N=N(N1)2Θ(N2)$1 + 2 + 3 + 4 +~...+~N = \frac{N(N-1)}2 \equiv \Theta(N^2)$
• Geometric sum: 1+2+4+8+ ...+ N=2N1Θ(N)$1 + 2 + 4 + 8 +~...+~N = 2N - 1 \equiv \Theta(N)$
• Sum of squares: 1+4+9+16+ ...+ N2Θ(N3)$1 + 4 + 9 + 16 +~...+~N^2 \equiv \Theta(N^3)$
• Sum of subarray lengths: (N)(1)+(N1)(2)+ ...+ (2)(N1)+(1)(N)=Θ(N3)$(N)(1) + (N-1)(2) + ~...+~(2)(N-1) + (1)(N) = \Theta(N^3)$
• Sum of logs: log1+log2+log3+ ...+ logN=logN!Θ(NlogN)$\log1 + \log2 + \log3 +~...+~\log N = \log N!\equiv \Theta(N \log N)$
• 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 increase N$N$ by 1$1$ the work doubles, this is Θ(2N)$\Theta(2^N)$ runtime
• Recurrence method: count the number of calls to a given function (known as a recurrence relation)
• For the code above, let C(N)$C(N)$ be the number of calls for a given N$N$
• Then we have C(1)=1$C(1) = 1$ and C(N)=2C(N1)+12C(N1)$C(N) = 2C(N-1) + 1 \equiv 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+ ...+ 2N1=Θ(2N)$C(N) = 1 + 2 + 4 + 8 +~... +~2^{N-1} = \Theta(2^N)$
• Binary search example:
• Solving with recurrence method, we have C(0)=0,C(1)=1,C(N)=1+C(N12)$C(0) = 0, C(1) = 1, C(N) = 1 + C(\frac{N-1}2)$
• This gives C(N)=1+1+ ...+ 1+0=k$C(N) = 1 + 1 + ~...+~1+0= k$ (there are k$k$ many 1$1$'s in the sum because of k$k$ many function calls)
• Observing the recurrence equation shows that this k=logN$k = \log N$
• Thus the runtime is Θ(logN)$\Theta (\log N)$
• Merge sort example:
• At top level we do N$N$ amount of work
• Then we split into two two N/2$N/2$ size groups and do N/2$N/2$ work for each
• Continue splitting down till group size =1$=1$
• Thus, at each level we do a total of N$N$ work, and we have a total of k=logN$k=\log N$ levels
• This gives a runtime of Θ(NlogN)$\Theta(N\log N)$
• Visualized in diagram below:
• Equivalently, using recurrence method, C(1)=1,C(N)=2C(N/2)+N$C(1)=1, C(N) = 2C(N/2) + N$
• This is solved below (lg=log2$\lg = \log_2$):