New answers tagged

1

$$\sum_{i = 0}^{n-2} (n - 1 -i) = (n -1) + (n-2) + ... + 2 + 1 = \frac{(n -1)n}{2}$$ It is the sum of the simplest arithmetic series.


1

Plug in the possible values of $i$ into the summation! You get: $$ (n-1) + (n-2) + \cdots + 2 + 1 $$ which is the sum of consecutive integers from 1 to $(n-1)$. This sum has a well-known formula: $$ {(\mbox {last term})\cdot(\mbox{last term} + 1)\over 2}={(n-1)n\over 2} $$


0

$$\frac{26}{672-x} + \frac{24}{372-x} = \frac{50}{480-x}$$ We could just go ahead and start solving this, but it will make the terms smaller if we let $2u=372-x$ $$\frac{26}{300+2u} + \frac{24}{2u} = \frac{50}{2u+108}$$ factoring a two out of top and bottom, we get $$\frac{13}{u+150} + \frac{12}{u} = \frac{25}{u+54}$$ We then want to get common fraction on ...


2

Let $f(n) = 3n^3+n^2+6^{\log_2 n} = 3n^3+n^2+n^{\log_2 6}$ and $g(n)=n^3$. Show both $f(n) = O(g(n))$ and $g(n) = O(f(n))$. This is exactly showing $f(n) = \Theta(g(n))$.


1

In general, because of Trakhtenbrot's theorem [0], these functions are not computable. Since with one binary relation symbol you can encode Turing machines with a logical sentence, your problem reduces to the busy beaver functions [1]. It is known that these functions grow ridiculously fast, and that they are not computable. [0] ...


1

This seems like a technicality, but basically is necessary for the proof to go through. Recall that the first part does not care about the language: it just states that $\sf Connectivity$ (on a $n$-vertex graph) is in $\sf DSPACE(\log^2 n)$. The second part, however, uses the fact that a state of the non-deterministic machine for a language in $L\in\sf ...


2

For any integer $m \ge 3$, define $\displaystyle\;g(n) = \begin{cases} m^{k},& n = 2k\\ m^{k+1}-1,& n = 2 k + 1\\ \end{cases}$. For any $n \ge 1$, we have $$\begin{align} \sum_{k=0}^{2n} g(k) &= 1 + \sum_{k=1}^n ( g(2k-1) + g(2k) ) = 1 + \sum_{k=1}^n (2\cdot m^k - 1)\\ &= 2\left(\frac{m^{n+1}-m}{m-1}\right) - (n-1) \le ...


2

Outline: Try to look first at the case $n=2^k$, and solve the recurrence $$ T(2^k) = 2^{2^k} T(2^{k-1})^2. $$ Expanding, you get $$ T(2^k) = 2^{2^k} (2^{2^{k-1}})^2 T(2^{k-2})^4 = 2^{2\cdot 2^k} T(2^{k-2})^4 = 2^{3\cdot 2^k} T(2^{k-3})^8 = \cdots = 2^{k\cdot 2^k} T(2^{0})^{2^k} $$ so that you obtain, using $T(2^0) = 1$, that $$ T(2^k) = 2^{k 2^k}. $$ ...


0

So it turns out that the question was actually easy to answer. Consider a minimal circuit of $2^{n}/n$ gates with $log(n)$ inputs; that is, no two nodes of the circuit compute the same function. This is certainly doable, since we are not limited by fan-out. Then it stands to reason that every functions on log(n) bits is computed by some node, which we can ...


0

I check the OP's example and tried a number of test functions, and couldn't find a function with $a < 4$. Here's what I did: If $g(n) = 2^n$, $\sum_{k=0}^{2n} g(k) =2^{2n+1}-1 =4\ 2^{2n-1}-1 <4\ 2^{2n-1} $. So that's OK. Let's try $g(n) = c^n$. $\sum_{k=0}^{2n} g(k) =\sum_{k=0}^{2n} c^n =\frac{c^{2n+1}-1}{c-1} $ so we want $\frac{c^{2n+1}-1}{c-1} ...


2

First, note that the answer cannot depend on $i$: $i$ is a dummy variable used as loop index (and so is $j$), so the answer can only depend on $n$. The inner loop performs two atomic operations, namely A[j] = A[j] + 1 and j = j + i so each inner iteration has constant cost $2$ (or similar, depending on the model of computation): anyway, ...


0

DTime: is a the set of time complexity classes for problems. It relates to running on a turing machine. The complexitity class e.g. P includes all problems that are solvable in polynomial time on a turing maschine (you can think of P as a higher boundary). Big O: This is a measure that can be used to measure the asymptotic performance of an algorithm. ...


0

We assume that the time consumption has reached the asymptotic behavior, that is that the time taken is actually $T(n) = T_0 n \log_2 n$. With this assumption you're correct the double size will not result in double time, it will be more than that. However the ratio can be arbitrarily close to doubling. We have: $$T(2n) = T_0 2n \log_2 (2n) = T_2 2n ...


1

You have that the time taken to complete a task is $T=kn\log n$. When $n=n_1$, the corresponding $T_1=kn_1 \log n_1$ You need to find $T_2=k(2n_1) \log (2n_1)$ $T_2=2kn_1 (\log 2 + \log n_1)$ $T_2=2kn_1 \log 2 + 2kn_1 \log n_1$ $T_2=2kn_1 \log n_1 \frac {\log 2}{\log n_1} + 2kn_1 \log n_1$ $T_2=2T_1 \frac {\log 2}{\log n_1} + 2T_1$ $T_2=2\left ...


0

You are looking at this recurrence relation: $T(n) = 2T(\sqrt{n})+1$ $T(1) = 1$ Suppose T is a solution. Then we have $T(1) = 2T(1) + 1$, so $1 = 3$. That is, this recurrence relation has no solution.


0

You can get as good an approximation as you want from $\sum\limits_{i = 1}^{3{n^3}} {\frac{{2n^3}}{i}} =2{n^3}\sum\limits_{i = 1}^{3{n^3}} {\frac{{1}}{i}} =2{n^3}H_{3n^3} =2{n^3}(\ln(3n^3)+\gamma+...) =2{n^3}(3\ln(n)+\ln(3)+\gamma+...) $.


0

Supposing $b > 1$ and $x \geq 1$, the pseudocode algorithm L := 0 while x >= b do L := L + 1 x := x / b end do return L returns $\lfloor \log_b x \rfloor$. (CS aside: If $b$ is an integer, this gives an exact result when all variables have type int. If the variables have type, e.g., float, likely this algorithm can return rounding errors.) ...


5

You're misunderstanding that. The problems of testing whether a number is even or ignoring the input and printing "false" are both in NP, and perfectly good polynomial-time algorithms are known for them. On the other hand, a polynomial-time algorithm for an NP-complete problem would (automatically and systematically) lead to polynomial-time algorithms for ...


3

"The problem is nonlinear non-convex programming problem which is hard to solve." "Hard" in the context of the time and space requirements of an algorithm or problem typically means "in exponential time (or space)". "The problem is an integer programming problem which is NP-hard." This means the problem is supposed to have the same ...


1

Let $k$ denote the length of the input value $n$. Since $k=\log_2n$, a complexity of $O(\sqrt{n})$ is equivalent to $O(\sqrt{2^k})$. Since $\sqrt{2^k}=2^{k/2}$, this complexity is obviously exponential in terms of input-length.


1

Strictly speaking, it is invalid to ask whether an abstract problem like integer factoring is in P. When deciding whether an algorithm runs in P time, we don't ask about the $n$, the number being factored (or equivalent), we ask about the length of the input. The length of the input depends on exactly how you've chosen to represent it. Instead, we have to ...


0

Why do you think the problem is solvable in $n^{1\over 2}$? Keep in mind that you have to find each factor, and testing "Does $x$ divide $y$?" (and computing $y/x$, if so) takes more than one step. (Also, $n$ here is the number of bits of the input, not the input itself. See bof's comment.) By the way, strictly speaking, we don't know that integer ...


0

The $n^n$ function is not an exponential as the basis varies. To prove $n!=o(n^n)$, let's evaluate the ratio: $$\frac{n!}{n^n}=\frac1n\cdot\frac2n\cdots\frac{n-1}n\cdot \frac nn <\frac 1n$$ since each factor $\dfrac kn$ is less than $1$ if $k<n$. This inequality implies $\;\displaystyle\lim_{n\to\infty}\frac{n!}{n^n}=0$.


0

From the definition of planar graphs - that you can always draw them on plane in such a way that edges just meet on nodes - I believe all polytrees are planar graphs (please correct me if I am wrong). Now since subgraph isomorphism of planar graphs has polinomial time algorithms available, I guess Sub-Polytrees isomorphism is also in the polynomial time ...


1

The premise that an $\mathcal{O}(n^2)$ function is more complex than an $\mathcal{O}(n)$ function is not quite right. The big-$\mathcal{O}$ notation acts more like an upper bound than like an exact equation. For example, $f(n) = n$ is $\mathcal{O}(n^2)$. Usually we'd say it's $\mathcal{O}(n)$, but it's certainly $\mathcal{O}(n^2)$ too; in fact ...


1

Some of the loops in the second loop are wasted, simplifying your code to sum = 0 for (i = 0; i < n; i++) for (j = 0; j < i; j++) for(k = 0; k < j ; k++) ++ sum which does the same thing slightly more efficiently, the mathematical formulation of the problem becomes: How many triplets $(i,j,k)$ are there such that $0\leq k < ...


2

You want to show $0 < \lim_{n \to \infty} \dfrac{f(n)}{n^{2}} < \infty$. That implies $f(n) \in \Theta(n^{2})$. Recall: $$\lim_{n \to \infty} \dfrac{f(n)}{n^{2}} = \lim_{n \to \infty} \dfrac{n^{2}}{n^{2}} + \lim_{n \to \infty} \dfrac{3n}{n^{2}}$$ I assume you can compute the each of these two new limits. Hint- can you cancel terms in the fractions ...


0

Reading from inside to outside: for(k = 0; k < n; k++) ++sum $$ s^n(0) $$ where $s(i) = i + 1$ and $s^n(0) = n$. for (j = 0; j < i * i; j++) $$ (s^n)^{i^2}(0) = s^{i^2 n}(0) $$ for (i = 0; i < n; i++) $$ S = s^{\sum_{i=0}^{n-1} i^2 n}(0) = s^{n \sum_{i=0}^{n-1} i^2}(0) = s^{n \frac{2(n-1)^3+3(n-1)^2+(n-1)}{6}}(0) = ...


0

Fix a value of $i$. There are $i^2$ values of $j$, and for each of them the innermost loop is executed $n$ times, so the ++sum is executed $i^2n$ times for that value of $i$. Thus, you want $$\sum_{i=1}^ni^2n=n\sum_{i=1}^ni^2=n\cdot\frac{n(n+1)(2n+1)}6=\frac16n^2(n+1)(2n+1)\;,$$ which is $O(n^4)$. By the way, a useful general fact is that ...


0

The inner loop is traversed $n$ times per traversal of the middle loop. The middle loop is traversed $i^2$ times for each $i$ through which the outer loop goes. The outer loop makes $i$ go from $1$ to $n$. The middle loop is therefore traversed $\sum_{i=1}^n i^2$ times which is $O(n^3)$. Thus, the total time -- i.e., the number of times the inner loop is ...


3

I cannot see the code, please paste the text into the question instead of the picture. The last step looks incorrect. Simplify $$ \sum_{j=1}^n j^2(j^2+1) = \sum_{j=1}^n j^4 + \sum_{j=1}^n j^2, $$ and the first term is $\Theta(n^5)$ while the second is $\Theta(n^3)$, so the sum is $$\Theta(n^5)+\Theta(n^3)=\Theta(n^5).$$ UPDATE Now you have $$ \sum_{i=1}^n ...


1

"polynomially larger" means that the ratio of the functions falls between two polynomials, asymptotically. Specifically, $f(n)$ is polynomially greater than $g(n)$ if and only if there exist generalized polynomials (fractional exponents are allowed) $p(n),q(n)$ such that the following inequality holds asymptotically: $$p(n)\leq \frac{f(n)}{g(n)}\leq q(n)$$ ...


1

Whenever you consider using $AA^T$ and "computation" in the same sentence, the answer will be "a bad idea". Consider the following: $$A = \begin{bmatrix} 1 & 1+x \\ 1+x & 1 \end{bmatrix}, \quad x = 10^{-8}.$$ Now, compute Moore-Penrose inverse via two methods, using Matlab: >> format long; >> x=1e-8; >> A = [ 1 1+x; 1+x 1] A = ...


2

Pick, non-deterministicly, an injection $f:V_1 \to V_2$ (in other words, pick, once and for all, a numbering of the vertices of $G_1$, and pick, non-deterministically, an ordered list of $|V_1|$ elements from $V_2$). Check whether this is an isomorphism onto its image subgraph. If not, pick another injection. Rinse and repeat. The isomorphism check is ...


0

That is true, because when we say a sequence $T(n) = O(f(n))$, where $f(n)$ is asymptotically positive, we mean that there exists $a > 0$, $N > 0$ so that for all $n > N$ \begin{align*} |T(n)| \leq af(n) \end{align*} You can check against this defining property for $T_1(n)-T_2(n)$


0

HINT: Use the states to keep track of the numbers of $a$s modulo $2$ and the number of $b$s modulo $3$. That is, use states $q_{0,0},q_{0,1},q_{0,2},q_{1,0},q_{1,1}$, and $q_{1,2}$, and design the automaton so that it is in state $q_{i,j}$ when the number of $a$s is of the form $2m+i$ and the number of $b$s is of the form $2n+j$ for some non-negative ...


0

Hint: This is such a nice task, so I will give only this little help. It is only about words from $L=\{a,b\}^*$ What FA would accept the words with a number of $a$ symbols divisible by $3$? What FA would accept the words with a number of $b$ symbols divisible by $2$? How could you construct a FA that combines both former FAs? How would one combine the ...



Top 50 recent answers are included