1
vote
Accepted
Time complexity of algorithm with three loops and if statement
Let's divide it in two parts: when the code enters the if and when it does not.
The if is executed when $n<i<n^3$ and $0\leq j <n$. This means that the values of $i$ which satisfy the ...
- 588
1
vote
Accepted
Why is the push operation in incrementally grown array stack is $O(n^2)$
The time for pushing in a stack of size $k$ is $O(k)$.
Thus the cost of all of the pushes is:
$$\sum_{k=1}^{n} k \ = \ \frac{n(n+1)}{2} \ = \ O(n^2) \ .$$
- 588
1
vote
Accepted
Explaination of incremental push's amortized time
It just means that the amortized time complexity is $O(n)$, amortized over $n$ pushes. The $[O(n^2)/n]$ indicates that the $O(n)$ amortized time comes from a total time complexity of $O(n^2)$ divided ...
- 588
1
vote
A $O(|E||V|)$ algorithm to determine if a graph is singly connected?
After doing more research, I believe the author of the preprint wasn't clear on the algorithm provided by CLRS. I think what CLRS meant is the following: for each $u \in V$ , run DFS-VISIT(u). In ...
- 67
1
vote
Accepted
A $O(|E||V|)$ algorithm to determine if a graph is singly connected?
Note that the algorithm by CLRS runs DFS for each vertex separately. Therefore, for the case you mentioned, the algorithm declares the graph as non-singly connected when performing DFS starting from ...
- 5,797
Only top scored, non community-wiki answers of a minimum length are eligible