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