91影视

Finding the general term for the following recurrence:

$T\left(n\right)=3T\left(n/2\right)+O\left(n\right)$

Let $O\left(n\right)鈮�cn$.

Thus, $T\left(n\right)$ can be present as follows:

$T\left(n\right)=3T\left(n/2\right)+cn$鈥︹�� (1)

$T\left(n\right)=\left(n/2\right)$in this formula it鈥檚 represent as follows:

$T\left(n/2\right)鈮�3\left(n/4\right)+\left(cn/2\right)$

$T\left(n/4\right)$can be represented as follows:

$T\left(n/2\right)鈮�3\left(n/8\right)+\left(cn/4\right)$

$T\left(n/8\right)$can be represented as follows:

$T\left(n/8\right)鈮�3\left(n/16\right)+\left(cn/8\right)$

Sub-equation (2) in equation (1). Hence,$T\left(n\right)$can be rewritten as follows:

role="math" localid="1658982909094" $$\begin{gathered} T\left(n\right)鈮�3\left(\left(n/4\right)+\left(cn/2\right)\right)+cn \\ 鈮�9\left(n/4\right)+3\left(cn/2\right)+cn \\ 鈮�9\left(n/4\right)+5\left(cn/2\right) \end{gathered}$$

Equation (5) can be written as follows:

$T\left(n\right)鈮�3^{2}T\left(n/2^2\right)+\left(2cn\left({\left(3/2\right)}^2-1\right)\right)$

The gives a detailed analysis for the formulation of solution as answer:

$$\begin{gathered} T\left(n\right)鈮�3^{2}T\left(n/2^2\right)+\left(2cn\left({\left(3/2\right)}^2-1\right)\right) \\ 鈮�9T\left(n/4\right)+\left(2cn\left(\left(9/4\right)-1\right)\right) \\ 鈮�9T\left(n/4\right)+\left(2cn\left(5/4\right)\right) \\ 鈮�9T\left(n/4\right)+cn\left(5/2\right) \\ 鈮�9T\left(n/4\right)+5\left(cn/2\right) \end{gathered}$$

Substitute equation in equation.

$$\begin{gathered} T\left(n\right)鈮�9\left(3T\left(n/8\right)+\left(cn/4\right)+5\left(cn/2\right)\right) \\ 鈮�27T\left(n/8\right)+9\left(cn/4\right)+5\left(cn/2\right) \\ 鈮�27T\left(n/8\right)+19\left(cn/4\right) \end{gathered}$$

Equation can be written as follows:

$T\left(n\right)鈮�3^{3}T\left(n/2^3\right)+\left(2cn{\left(3/2\right)}^3-1\right)$

Note:

Explanation for the representation of equation as equation has been represented as follows:

$$\begin{gathered} T\left(n\right)鈮�3^{3}T\left(n/2^3\right)+\left(2cn\left({\left(3/2\right)}^3-1\right)\right) \\ 鈮�27T\left(n/8\right)+\left(2cn\left(\left(27/8\right)-1\right)\right) \\ 鈮�27T\left(n/8\right)+\left(2cn\left(19/8\right)\right) \\ 鈮�27T\left(n/8\right)+cn\left(19/4\right) \end{gathered}$$

Substitute equation (4) in equation (7).

$$\begin{gathered} T\left(n\right)鈮�27\left(3T\left(n/16\right)+\left(cn/8\right)\right)+19\left(cn/4\right) \\ 鈮�81T\left(n/16\right)+65\left(cn/8\right) \end{gathered}$$

Equation can be written as follows:

$T\left(n\right)鈮�3^{4}T\left(n/2^4\right)+\left(2cn\left({\left(3/2\right)}^4-1\right)\right)$

This following is an explanation for such formulation for equation into equation:

$$\begin{gathered} T\left(N\right)鈮�3^{4}T\left(n/2^4\right)+\left(2cn\left({\left(3/2\right)}^4-1\right)\right) \\ 鈮�81T\left(n/16\right)+\left(2cn\left(\left(81/16\right)-1\right)\right) \\ 鈮�81T\left(n/16\right)+\left(2cn\left(65/16\right)\right) \\ 鈮�81T\left(n/16\right)+2cn\left(65/16\right) \\ 鈮�81T\left(n/16\right)+65\left(cn/8\right) \end{gathered}$$

Commonly, it will be written as follow:

$T\left(n\right)鈮�3^{k}T\left(n/2^k\right)+2cn\left({\left(3/2\right)}^k-1\right)$

Substituting $k={\log }_{n}n$ then,

$$\begin{gathered} T\left(n\right)鈮�n^{{\log }_{2}3}T\left(n/2^{{\log }_{2}n}\right)+2cn\left({\left(3/2\right)}^{{\log }_{2}n}-1\right) \\ 鈮�n^{{\log }_{2}3}T\left(n/2^{{\log }_{2}n}\right)+2cn\left(n^{{\log }_{2}3}/n^{{\log }_{2}2}-1\right) \\ 鈮�n^{{\log }_{2}3}T\left(n/n^1\right)+2cn\left(n^{1.58}/n^1-1\right) \\ 鈮�n^{{\log }_{2}3}T\left(1\right)+2cn\left(\left(n^{1.58}-n\right)/n\right) \\ 鈮�n^{{\log }_{2}3}T\left(1\right)+2cn\left(n^{0.58}/n\right) \\ 鈮�n^{{\log }_{2}3}T\left(1\right)+2c{n}^{0.58} \end{gathered}$$

$T\left(1\right)$can be written as $o\left(1\right)$ and neglect the constant term $2c{n}^{0.58}$. Hence, the above equation becomes,

$$\begin{gathered} T\left(n\right)鈮�n^{{\log }_{2}3}O\left(1\right) \\ =O\left(n^{{\log }_{2}3}\right) \end{gathered}$$

Therefore, when substituting $k={\log }_{2}n$ in the general representation of $T\left(n\right)$, the final answer $O\left(n^{{\log }_{2}3}\right)$ is obtained.

Finding the general $k$term for the following recurrence:

$T\left(n\right)=T\left(n-1\right)+O\left(1\right)$

Let role="math" localid="1658987670332" $o\left(n\right)鈮�cn$ thus, $T\left(n\right)$ it will be represented as follows:

$T\left(n\right)鈮�T\left(n-1\right)+c$

$T\left(n-1\right)$can be represented as follows:

$$\begin{gathered} T\left(n-1\right)鈮�T\left(\left(n-1\right)-1\right)+c \\ 鈮�T\left(n-2\right)+c \end{gathered}$$

$T\left(n-2\right)$it will be represented as follows:

$$\begin{gathered} T\left(n-2\right)鈮�T\left(\left(n-2\right)-1\right)+c \\ 鈮�T\left(n-3\right)+c \end{gathered}$$

Substitute equation (2) in equation (1). Hence,$T\left(n\right)$can be rewritten as follows:

$$\begin{gathered} T\left(n-2\right)鈮�T\left(n-2\right)+c+c \\ 鈮�T\left(n-2\right)+2c \end{gathered}$$

In general,$T\left(n\right)$can be written as follow:

$T\left(n\right)鈮�T\left(n-k\right)+kc$

Substitute $k=n$ in equation (5),$T\left(n\right)$can be written as follows:

$$\begin{gathered} T\left(n\right)鈮�T\left(n-n\right)+nc \\ T\left(n\right)=T\left(0\right)+nc \\ =O\left(n\right) \end{gathered}$$

Therefore, $T\left(n\right)=O\left(n\right)$ and it can be obtained by substituting $k=n$.