Identifying Code Runtime

Linear

If we are adding or subtracting by some constant, it is linear.

for (int i=0; i<n; i++)
  cout << "wow";
``
$$
\sum_{i=0}^{n-1} = n = \Theta(n)
$$
 
```cpp
for (int i=2; i<n; i++) 
  cout << "wow";

$$\sum _{i=2}^{n-1}\Theta (1)=n-2=\Theta (n)$$

for (int i=0; i<n/2; i++)
  cout << "wow";
``
$$
\sum_{n/2 - 1}^{i=0} \Theta(1) = \frac{n}{2} = \Theta(n)
$$
 
```cpp
for (int i=0; i<n; i=i+3)
  cout << "wow";

$$\sum _{n-1}^{i=0}\Theta (1)=\frac{n}{3}=\Theta (n)$$

“cpp
for (int i=n; i>0; i—)
cout << “wow”;

$$
\text{Missing answer} = \Theta(n)
$$

# Logarithmic

If we are multiplying or dividing by some constant, it is logarithmic.

```cpp
for (int i=n; i>0; i=i/2)
  cout << "wow";

$${\log }_{2}n=\Theta (\log n)$$

for (int i=1; i<n; i=i*2)
  cout << "wow";

$${\log }_{2}n=\Theta (\log n)$$

for (int i=m; i>0; i=i/10)
  cout << "wow";

$${\log }_{10}n-\Theta (\log n)$$

Quadratic

If there are nested loops, multiply the runtime of each loop.

for (int i=0; i<n; i++)
  for (int j=0; j<n; j++)
    cout << "wow";

$$\sum _{i=0}^{n-1}\sum _{j=0}^{n-1}\Theta (1)=\sum _{i=0}^{m-1}n=n^2=\Theta (n^2)$$

for (int i=0; i<n; i++)
  for (int j=0; j<i; j++)
    cout << "wow";

$$\sum _{i=0}^{n-1}\sum _{j=0}^{i-1}\Theta (1)=\sum _{i=0}^{n-1}i=0+1+2+3+\cdots +n-1=?$$

Gauss’ Formula

${\sum }_{i=1}^{n}i=\frac{n(n+1)}{2}$

$$\sum _{i=1}^{n-1}i=\frac{(n-1)(n-1+1)}{2}=\frac{n(n-1)}{2}=\frac{n^2-n}{2}=\Theta (n^2)$$

Weird ones

for (int i=0; i<n; i++)
  for (int j=1; j<n; j=j*2)
    cout << "wow";

$$n\cdot {\log }_{2}n=\Theta (n\log n)$$

for (int i=0; i<n; i++)
  for (int j=1; j<i; j=j*2)
    cout << "wow";

$$\begin{gathered} \sum _{i=0}^{n-1}{\log }_{2}i \\ ⟹\sum _{i=1}^n{\log }_{2}i={\log }_{2}1+{\log }_{2}2+{\log }_{2}3+\cdots +{\log }_{2}n={\log }_2(1\cdot 2\cdot \cdots \cdot n)={\log }_2(n!) \\ \sum _{i=1}^n{\log }_{2}i\approx \sum _{i=1}^n\ln i\approx {\int }_1^n\ln xdx=x\ln x-x+C\text{REQUIRES LINE FROM 1 to n}=(n\ln n-n+C)-(1\ln 1-1+C)=n\ln n-n+1=\Theta (n\log n) \end{gathered}$$

${\log }_a(n!)=\Theta (n\log n)$

Non nested

Just add them instead of multiply

for (int i=0; i<n; i++)
  cout << "wow";
 
for (int i=0; i<n; i++)
  cout << "wow";

$$\Theta (n)+\Theta (\log n)=\Theta (n)$$