0

My Code:

\documentclass[12pt,a4paper]{report}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{qtree}
\usepackage{tikz-qtree}
\usepackage{wrapfig}
\usepackage{drawstack}

\usepackage{geometry}
\geometry{a4paper, left=2cm, right=2cm, top=2cm, bottom=2cm, headsep=1cm, footskip=1cm}
\renewcommand{\familydefault}{\sfdefault}
\graphicspath{{images/}}

%Declaring Ceil and Floor functions
\usepackage{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}

%Declaring styles for Stacks
\tikzstyle{freecell}=[fill=none]
\tikzstyle{occupiedcell}=[fill=none]

\author{Somenath Sinha}
\title{Algorithms}
\date{November 2016}

\begin{document}    
    \maketitle
    \tableofcontents

    \input{"Time and Space Analysis"}
\chapter{Time and Space Analysis}
\setlength{\parskip}{1em}

\section{Analysing Space Complexity of Iterative and Recursive Algorithms}
To analyse the space complexity of an algorithm, we find out how much memory will be required to calculate the output in terms of the size of the input, $n$. Note that sometimes there'll be a trade-off between the time and space complexity, i.e., to improve the time complexity the space complexity may increase, and vice versa.

\subsection{Calculating the Space Complexity of an Iterative Algorithm}
\begin{tabular}{lc}
    \begin{minipage}{0.3\textwidth}
        \begin{verbatim}
        A(A,1,n)
        {
            int i;
            for(i=1 to n)
                A[i]=0;
        }
        \end{verbatim}
    \end{minipage}
    &
    \begin{tabular}{p{0.65\textwidth}}
        Consider an array A of size $n$, provided as input to the algorithm. Let it use a single variable i, of size $1$ to process the input. Then the total space required is $n+1$. However, since the array is provided as input, we won't consider its size in the complexity calculations. Thus this algorithm has a total space complexity of $\operatorname{O}(1)$.
    \end{tabular}
\end{tabular}
\vspace{10pt}\hrule
\begin{tabular}{lc}
    \begin{minipage}{0.26\textwidth}
        \begin{verbatim}
        A(A,1,n)
        {
            int i,j=10;
            for(i=1 to j)
                A[i]=0;
        }
        \end{verbatim}
    \end{minipage}
    &
    \begin{tabular}{p{0.65\textwidth}}
        Here, two variables i \& j are used to evaluate the output. Hence, the space complexity is still $\operatorname{O}(1)$ as the space complexity is independent of the size of the input $n$. Regardless of the input, the program will always use exactly two variables.
    \end{tabular}
\end{tabular}
\vspace{10pt}\hrule
\begin{tabular}{lc}
    \begin{minipage}{0.26\textwidth}
        \begin{verbatim}
        A(A,1,n)
        {
            int i;
            create B[n];
            for(i=1 to n)
                B[i]=A[i];
        }
        \end{verbatim}
    \end{minipage}
    &
    \begin{tabular}{p{0.65\textwidth}}
        Now, we're creating an array of size $n$ to copy the data from the original array A to the new array B. Again, the variable i also requires space of size $1$ to store its data. Thus, the total space required is $n+1$ and the time complexity is $\operatorname{O}(n)$.
    \end{tabular}
\end{tabular}
\vspace{10pt}\hrule
\begin{tabular}{lc}
    \begin{minipage}{0.3\textwidth}
        \begin{verbatim}
        A(A,1,n)
        {
            int i,j;
            create B[n,n];
            for(i=1 to n)]
                for(j=1 to n)
                    B[i,j]=A[i];
        }
        \end{verbatim}
    \end{minipage}
    &
    \begin{tabular}{p{0.61\textwidth}}
        We're creating a two dimensional array of size $n\times n$ thus requiring a space of $n^2$. Additionally, the space reqired by the variables i and j is $2$. Thus total space required is $=n^2+2$. So, the total space complexity is $\operatorname{O}(n^2)$.
    \end{tabular}
\end{tabular}
\vspace{10pt}\hrule

\subsection{Calculating the Space Complexity of a Recursive Algorithm}
\begin{tabular}{lc}
    \begin{minipage}{0.25\textwidth}
        \begin{verbatim}
        A(n)
        {
            if(n>=1)
            {
                A(n-1);
                pf(n);
            }
        }
        \end{verbatim}
    \end{minipage}
    &
    \begin{tabular}{p{0.7\textwidth}}
        Here, A is calling itself right at the beginning of the program. Thus, it is called "Head Recursion". If A would have been called at the end of the program, it'd have been called "Tail Recursion". In "Body Recursion" the recursive statement would be present anywhere in the body other than the beginning or the end. The condition inside of the if statement is called the anchor/halting condition.Whenever the size of the program is small, we should use the recursion tree method to evaluate the space complexity. Otherwise, use stack method to do the same.
    \end{tabular}
\end{tabular}
\subsubsection{Recursion Tree Method}
\begin{tabular}{cc}
    \begin{minipage}{0.4\textwidth}
        \Tree [.A(3) [.A(2) [.A(1)  [.A(0) ]
                                    [.pf(1) ] ]
                            [.pf(2) ] ]
                     [.pf(3) ] ]
    \end{minipage}
    &
    \begin{minipage}{0.3\textwidth}
        \begin{drawstack}
            \cell{A(0)}
            \cell{A(1)}
            \cell{A(2)}
            \startframe
            \cell{A(3)}
            \finishframe{k Units of memory}
        \end{drawstack}
    \end{minipage}
\end{tabular}

Let us consider that the value of $n=3$. Then we'd need 4 recursive calls as shown in the figure. The last condition fails the halting condition and stops the execution. Thus for a parameter of $n$, the functions needs $n+1$ recursive calls. All the recursive calls of A will be pushed down to a stack. We traverse the recursion tree form top to bottom, left to right. When traversing, if the node is a function call, we push it onto the stack. If however, it is something to be executed, we do so immediately. This means, At first, when the execution starts, we first visit the function A(3). It is pushed onto the stack.

Next, immediately after the "if" condition (which it passes as $n=3$), A(2) is called. This adds the function A(2) onto the stack. Similarly, the function A(1) is added to the stack. Finally the function A(0) is added and simultaneously popped off the stack, as it has nothing to execute. Next we move to the right node of the tree containing the code "pf(1)". This causes 1 to be printed. Now A(1) has nothing further to execute, and is popped off. Similarly, 2 and 3 are also printed, followed by the popping of A(2) and A(3) respectively.

Here, we don't have to analyse the space complexity using the space occupied by the variables (in this example, there are none). We have to calculate the space complexity by analysing the height of the stack. So, if the input size is $n$, there will be $n+1$ recursive calls, each costing $k$ units of memory. Thus the total memory used is $k*(n+1)$. Thus the space complexity is $\operatorname{O}(kn) = \operatorname{O}(n)$.

\vspace{10pt}\hrule

Further, to calculate the time complexity of the same problem, we formulate the recursion equation. We assume the time complexity to solve A(n) is given by $\operatorname{T}(n)$. Next, the function is calling A(n-1), the time complexity of which is $\operatorname{T}(n-1)$. Next the printing takes constant time $c$ denoted by $1$ in the equation. \[ \operatorname{T}(n) = \operatorname{T}(n-1) +1 \]
Here, we can't apply Master's Theorem as $b$ isn't available. So, we use back substitution method.
\begin{equation*}
\begin{aligned}
\operatorname{T}(n) &= \operatorname{T}(n-1) +1 \\
\operatorname{T}(n-1) &= \operatorname{T}(n-2) +1 \\
\operatorname{T}(n-2) &= \operatorname{T}(n-3) +1 \\
\operatorname{T}(n) &= (\operatorname{T}(n-2) +1)+1 \\
&= ((\operatorname{T}(n-3) +1)+1)+1 \\
&= \operatorname{T}(n-n) +n \\ 
\text{[T(0) is the halting condition. }& \text{Here the work done is 1(for the if condition checking)]}\\
&=n+1 = \operatorname{O}(n).
\end{aligned}
\end{equation*}
\hrule
\begin{tabular}{cc}
    \begin{minipage}{0.25\textwidth}
        \begin{verbatim}
        A(n)
        {
            if(n>=1)
            {
                A(n-1);
                pf(n);
                A(n-1);
            }
        }
        \end{verbatim}
    \end{minipage}
    &
    \begin{minipage}{0.6\textwidth}
        \begin{drawstack}
            \cell{A(0)}
            \cell{A(1)}
            \cell{A(2)}
            \startframe
            \cell{A(3)}
            \finishframe{k Units of memory}
        \end{drawstack}
    \end{minipage}
\end{tabular}

\begin{tikzpicture}[scale=0.9]
    \Tree [.A(3) [.A(2) [.A(1)  [.A(0) ]
    [.pf(1) ] 
    [.A(0) ] ] 
    [.pf(2) ] 
    [.A(1)  [.A(0) ]
    [.pf(1) ] 
    [.A(0) ] ] ]
    [.pf(3) ] 
    [.A(2) [.A(1)  [.A(0) ]
    [.pf(1) ] 
    [.A(0) ] ] 
    [.pf(2) ] 
    [.A(1)  [.A(0) ]
    [.pf(1) ] 
    [.A(0) ] ] ] ]
\end{tikzpicture}

In this, the function A() is called $2^{n+1}-1=15$ times. The execution starts with A(3), and progresses from top to bottom, and left to right. After A(3) is added to the stack, it is followed by pushing A(2), A(1) and A(0) to the stack. A(0) is immediately popped off, as it has nothing to execute. Then, 1 is printed, followed by A(0) being pushed and popped off again. Then, as the branches of the first A(1) are exhausted, it is popped off. Next, 2 is printed due to A(2)'s code. Now, the entire operation for A(1) is repeated for the second instance of A(1), and so on. The output printed is 1213121.

So, as we can see, even thought the function A() is called 15 times for A(3), the actual cells in the stack required are merely 4, since they're vacated(popping of the functions) and reoccupied repeatedly. Thus the stack requires $n+1$ cells only. So the space complexity assuming each cell in the stack to be of $k$ memory units, is k*(n+1)= $\operatorname{O}(nk)=\operatorname{O}(n)$.

Note that here, a pattern emerges, such as A(2) will always print "121" and A(1) will always print 1. So, instead of running the same code multiple times, we could store the output after running it for the first time in a table and simply produce it when needed again. This dynamically deciding whether to run the code or simply produce the output is called Dynamic Programming. 

\vspace{10pt}\hrule

To calculate the time complexity, we've to form the recursive equation, which is:

    \begin{tabular}{cc}
    \begin{minipage}{0.25\textwidth}
        \begin{equation*}
            \begin{aligned}
                \operatorname{T}(n)&=2\operatorname{T}(n-1)+1 \\
                \operatorname{T}(n-1)&=2\operatorname{T}(n-2)+1 \\
                \operatorname{T}(n-2)&=2\operatorname{T}(n-3)+1 \\
            \end{aligned}
        \end{equation*}
    \end{minipage}
    &
    \begin{minipage}{0.68\textwidth}
        \begin{equation*}
            \begin{aligned}
                \operatorname{T}(n)&=2\operatorname{T}(n-1)+1 \\
                &=2(2\operatorname{T}(n-2)+1)+1 \\
                &=4\operatorname{T}(n-2)+2+1 \\
                &=4(2\operatorname{T}(n-3)+1)+3 \\
            \end{aligned}
        \end{equation*}
        This is a test to see how far this particular line should be able to extend let's see if this goes any further.
    \end{minipage}
\end{tabular}
Now, the only way this recursive equation stops is when T(0) is encountered, when $k=n$. And T(0)=1, since the if condition inside is checked even when $n=0$. So, we have:
\begin{align*}
    \operatorname{T}(n)&=2^n\operatorname{T}(0)+2^n-1 \\
    &= 2^n*2 -1 \\
    &= 2^{n+1}-1 \\
    &= \operatorname{O}(2^{n+1}) = \operatorname{O}(2^n)
\end{align*}
\hrule

Output:

Overlap in minipage

Notice how the text overlaps with the equation? Why does this happen? How do I prevent this? What is the correct way to decide the size of the minipages? Am I not supposed to use minipages inside tabular? I have no other way since I can't directly use equation env inside tabular.

  • please post a complete document that produces the shown image not just a fragment. In particular it depends crucially on the text width which you have not shown in the code. – David Carlisle Nov 4 '16 at 13:21
  • It looks like you have \tabcolsep set to zero but as you have not shown any code to reproduce the problem, it is hard to be sure. – David Carlisle Nov 4 '16 at 13:23
  • First, why do you use 'c' columns with a minipage inside rather than p{} columns? – Piet van Oostrum Nov 4 '16 at 13:36
  • @PietvanOostrum I'm new to latex (been using it for 5 days) and have no how to do it better. Sorry. – Somenath Sinha Nov 4 '16 at 13:41
  • 2
    @SomenathSinha It really pays off studying LaTeX first before writing complicated documents like this. It will save you a lot of headaches. – Piet van Oostrum Nov 4 '16 at 13:55
1
\documentclass{article}
\usepackage{amsmath}

\begin{document}

\begin{tabular}{p{0.35\textwidth}p{0.53\textwidth}}
        \begin{equation*}
            \begin{aligned}
                \operatorname{T}(n)&=2\operatorname{T}(n-1)+1 \\
                \operatorname{T}(n-1)&=2\operatorname{T}(n-2)+1 \\
                \operatorname{T}(n-2)&=2\operatorname{T}(n-3)+1 \\
            \end{aligned}
        \end{equation*}
    &
        \begin{equation*}
            \begin{aligned}
                \operatorname{T}(n)&=2\operatorname{T}(n-1)+1 \\
                \operatorname{T}(n-1)&=2\operatorname{T}(n-2)+1 \\
                \operatorname{T}(n-2)&=2\operatorname{T}(n-3)+1 \\
            \end{aligned}
        \end{equation*}
        This is a text to see how far this particular line should be able to extend let's see if it goes any further.
\end{tabular}

\end{document}
  • You can't directly use equation env inside a tabular without using minipages. Please refer to How to put a formula into a table cell to see what I mean. – Somenath Sinha Nov 4 '16 at 13:51
  • 2
    With p{} columns you can. This is more or less the same as a minipage (with slightly less functionality) but is more like it's done in LaTeX. – Piet van Oostrum Nov 4 '16 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.