New answers tagged

2

Typical implementations of Merge sort use a new auxiliary array split into two parts, a left part and a right part. This extra space is the reason for the O(n) space complexity. During the sort section of the algorithm we have the following two new auxiliary arrays created for additional space. int leftPartition[] = new int[ leftPartitionSize ]; int ...


2

Assume the maximum length of strings is $k$, which is less than some constant. Here is a simple algorithm that runs in linear time and $O(1)$ space complexity. The strategy is simply counting strings by length followed by in-place rearrangement. Assume the input is an array $s[0], s[1], \cdots, s[n-1].$ Count the number of strings of length $i$. Store it ...


4

Because, if you only use $f(n)$ tape cells, there are at most $|\Sigma|^{f(n)}$ possible strings you can have written on the tape, at most $f(n)$ different places the tape head could be, and at most $|Q|$ different states the Turing machine could be in. That means there are at most $|Q|\,f(n)\,|\Sigma|^{f(n)}$ different configurations for the machine. If ...


2

Consider all the possible configurations of a Turing machine $T$: if $S$ is the number of its states, $\Sigma$ is its alphabet, including the empty character, and $f(n)$ is an upper bound on the space used, then you only have $$ |S| \cdot f(n) \cdot |\Sigma|^{f(n)} = |S| \cdot f(n) \cdot 2^{f(n) \cdot \log_2 |\Sigma| } = 2^{O(f(n))} $$ configurations (where ...


2

Let's build some recursive function. We start picking any vertex of the tree $T$ and call it $R$ as root. If $R$ was removed, you would get a forest of several sub-trees. Every subtree $T_k$ has a vertex $k$ connected to $R$ in $T$. Now there are 3 types of paths contributing to the sum of cost of paths $N(R)$: $I(R)$, the cost of all inner paths of the ...


Top 50 recent answers are included