\documentclass[11pt]{article}

\usepackage{amsmath}

\usepackage{amssymb}

\usepackage[a4paper,body={},top=1.5cm, left=2.5cm,right=1cm,bottom=2.5cm,nohead]{geometry}

%=============== Begin Document ==================

\begin{document}

\begin{center}{\em

{\LARGE University of Bahrain}\[0.08in]

College of Information Technology\

Department of Computer Science\[0.08in]

ITCS255 Discrete Structure II\[0.05in]

First Semester 2024/2025\

Home Assignment #3}

\bigskip

\renewcommand{\arraystretch}{1.4} % increase row height

\begin{tabular}{|l||p{3.7in}|c|} \hline

Student Name & & GRADE\ \hline

Student ID & & \ \cline{1-2}

Section & & \\hline

\end{tabular}

\end{center}

\begin{enumerate}

\item Question #1\

{\bf Answer.}\\

\item Question #2\

{\bf Answer.}\

Given T(1) = 1, T(n) = 3T(n/2) + n log n\

Let n = $2^k$, k = 0,1,2, ... , $\infty$\\

T($2^1$) = 3T(1) + 2 $\cdot$ log(2)\\

T($2^2$) = 3T($2^1$) + $2^2$ $\cdot$ log($2^2$)\

= 3(3T(1) + 2 $\cdot$ log(2)) + $2^2$ $\cdot$ log($2^2$)\

= $3^2$T(1) + 3 $\cdot$ 2 $\cdot$ log(2) + $2^2$ $\cdot$ log($2^2$)\\

T($2^3$) = 3T(4) + $2^3$ + log($2^3$)\

= 3($3^2$T(1) + 3 $\cdot$ 2 $\cdot$ log(2) + $2^2$ $\cdot$ log($2^2$)) + $2^3$ $\cdot$ log($2^3$)\

= $3^3$T(1) + $3^2$ $\cdot$ 2 $\cdot$ log(2) + 3 $\cdot$ $2^2$ $\cdot$ log($2^2$) + $2^3$ $\cdot$ log($2^3$)\\

T($2^4$) = 3T(8) + $2^4$ . log($2^4$)\

= 3($3^3$T(1)+$3^2$ $\cdot$ 2 $\cdot$ log(2) + 3 $\cdot$ $2^2$ $\cdot$ log($2^2$) + $2^3$ $\cdot$ log($2^3$)) + $2^4$ $\cdot$ log($2^4$)\

= $3^4$T(1) + $3^3$ $\cdot$ 2 $\cdot$ log(2) + $3^2$ . $2^2$ $\cdot$ log($2^2$) + 3 $\cdot$ $2^3$ $\cdot$ log($2^3$) + $2^4$ $\cdot$ log($2^4$)\\

[

T(2^k) = 3^k T(1) + \sum_{i=0}^{k - 1} 3^i \cdot 2^{k-i} \cdot

\log(2^{k-i})

]

[

= 3^k T(1) + \sum_{i=0}^{k - 1} 3^i \cdot 2^{k-i} \cdot (k-i) \cdot \log(2)

]

[

= 3^k T(1) + (2^k \cdot \log(2)) \sum_{i=0}^{k-1} 3^i \cdot 2^{-i} \cdot (k-i)

]

[

= 3^k T(1) + (2^k \cdot \log(2)) \sum_{i=0}^{k-1} (\frac{3}{2})^i \cdot (k-i)

]

[

= 3^k T(1) + (2^k \cdot \log(2)) \sum_{i=0}^{k-1} k(\frac{3}{2})^i - \sum_{i=0}^{k-1} i(\frac{3}{2})^i

]

[

= 3^k T(1) + (2^k \cdot \log(2)) k\sum_{i=0}^{k-1} (\frac{3}{2})^i - \sum_{i=0}^{k-1} i(\frac{3}{2})^i

]

[

= 3^k T(1) + (2^k \cdot \log(2)) k \cdot \frac{(3/2)^k-1}{(3/2)-1} - \sum_{i=0}^{k-1} i(\frac{3}{2})^i

]

since

[ \sum_{i=0}^{k-1} ix^i = \frac{x-kx^k+(k-1)x^{k+1}}{(1-x)^2}

]

then

[ \sum_{i=0}^{k-1} i(\frac{3}{2})^i =

\frac{\frac{3}{2}-k(\frac{3}{2})^k+(k-1)(\frac{3}{2})^{k+1}}{

(1-\frac{3}{2})^2}

]

=

[

= 3^k T(1) + (2^k \cdot \log(2)) k \cdot \frac{(3/2)^k-1}{(3/2)-1} - \frac{\frac{3}{2}-k(\frac{3}{2})^k+(k-1)(\frac{3}{2})^{k+1}}{

(1-\frac{3}{2})^2}

]

=

[

= 3^k T(1) + 2k \log(2) \cdot 2^k \left( \left( \frac{3}{2} \right)^k - 1 \right) - 6 + (-2k + 6) \left( \frac{3}{2} \right)^{k}

]

$n = 2^k$\

log both sides:\

$\log_2n = \log_22^k$\

= $\log_2n = k\cdot \log_22$\

= k = $\log_2n$\

By substituting:\

[

= 3^{\log_2 n} T(1) + 2 \log_2 n \log_2(2) \cdot n \left( \left( \frac{3}{2} \right)^{\log_2 n} - 1 \right) - 6 + \left(-2 \log_2 n + 6\right) \left( \frac{3}{2} \right)^{\log_2 n}

]

\end{enumerate}

\end{document}

is it correct?