# Tag Info

4

Let's consider the outer two loops first. For a fixed value of $i$, the number of iterations of the middle loop is exactly $n-1 - (i+1) + 1 = n - i -1$. Since $i$ ranges from $0$ to $n-1$ (in the outer loop), the overall number of iterations of the middle loop is: $$\sum_{i=0}^{n-1} (n - i -1) = \sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}.$$ For each of those ...

4

Each time add $i$ to $s$ and increase $i$ by one, up to reach to $n$. Hence, if you find the $k$ such that $s = 0 + 1 + 2 + ... + k$ be equal to $n$, you can find the number of running loop. As $1 + 2 + \ldots + k = \frac{k(k+1)}{2}$, you need to solve this equation $\frac{k(k+1)}{2} = n$. $$k^2 + k -2n = 0 \Rightarrow k = \frac{-1 + \sqrt{1+8n}}{2} = \... 2 For all n\geq 1, 56n^2+106n+48> 56n^2> n^2 and \log (264n^2+200)> \log 264n^2>\log n, so$$(56n^2+106n+48)\log(264n^2+200) > n^2\log n\,,$$i.e., you can take c_1=1. Also for all n\geq 1, 56n^2+106n+48\leq 56n^2+106n^2+48n^2 = 210n^2 and, for all n\geq 200, 264n+200 < 265n so \log(264n^2+200) < \log 265n^2 = 2\log n + \... 2 I just found the answer myself. In this paper: Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs‏". Technical reports, HP research labs. in section 5, the authors show that the Hopcroft-Karp algorithm in fact solves the following problem: given an integer s, find matchings with 1,\ldots,s edges. The ... 1 \sum_{i=1}^k 2^i=\Theta(2^k) and you have k\approx\log n, so the sum is \Theta(2^{\log n})=\Theta(n). 1 1 For the first case, you had the right idea, but just had some algebra mistakes. for i=1..n j=1 while j*j <= i: j = j + 1 Let T(n) be the time complexity.$$T(n) = \sum_{i=1}^n\sum_{j=1}^\sqrt{i}1\leq \sum_{i=1}^n\sqrt{n}=\leq n^{3/2}= O(n^{3/2})$$2 I'm assuming you meant the pseudocode below since it is more analogous to ... 1 Let's take a look at the case of size 7 first. Here, we want to show a linear upper bound for T(n). Thus, we choose the recurrence relation T(n) \leq T(n / 7) + T(5 / 7 n) + dn (remember, it is an upper bound). We guess that the solution is of the form T(n) \leq cn for some constant c and prove it with induction:$$T(n) \leq T(n / 7) + T(5 / 7 \cdot ...

1

That's right. This for loop stops when: $$3^i < n^3 \rightarrow i<3\log(n)$$ Which implies the complexity of this for loop is $O(\log(n))$.

Only top voted, non community-wiki answers of a minimum length are eligible