New answers tagged runtime-analysis
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 ...
0
When measuring comparisons, we usually only charge comparisons of elements of the array (more accurately, we charge comparisons for the datatype of array elements, but not of array indices). In the example of linear search, at each iteration you are comparing one element of the array to the input element being searched. So in total, you are making exactly $n$...
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)$.
0
Process of elimination
A, perhaps, easier method to derive the time complexity is by process of elimination. This is especially the case if you get this type of question in a multiple choice exam. That said, this method is far from as rigorous as OmG's answer.
Okay, we know that A is upper-bounded by O(n), as we increment $s$ by more than 1 in each ...
0
After the first sqrt(n) iterations, s is increased by more than sqrt(n) in each iteration. Therefore at most 2 sqrt(n) iterations are needed to make s > n.
On the other hand, in the first sqrt(n) iterations, s is increased at most by sqrt(n) in each iteration, so sqrt(n) iterations are not enough.
This means the number of iterations is $\Theta(n^{1/2})$.
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} = \...
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
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 ...
0
$c_1 = 56$ works for all n.
Let n >= 265, then 200 <= $n^2$, $264n^2 + 200 <= n^3$, the logarithm is less than 3 log n, $56n^2 + 106n + 48 <= 56n^2 + n^2 + n^2 = 58n^2$, so you can pick $c_2 = 58*3 = 174.
0
It's sometimes more convenient to work with the limit definitions.
To prove the statement, you can break it down into proving that $f(n) = O(g(n))$ and that $f(n) = \Omega(g(n))$. In your case, it's straightforward to compute $\lim_{n \to \infty} f(n)/g(n)$. I believe that this will turn out to be a positive three-digit constant less than infinity and ...
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 + \...
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))$.
Top 50 recent answers are included
