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 ...
SilvioM's user avatar
  • 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) \ .$$
SilvioM's user avatar
  • 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 ...
SilvioM's user avatar
  • 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 ...
Hugh Mann's user avatar
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 ...
Inuyasha Yagami's user avatar

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