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 ...
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) \ .$$
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 ...
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 ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
algorithm-analysis × 1991algorithms × 964
runtime-analysis × 584
time-complexity × 229
asymptotics × 210
sorting × 158
complexity-theory × 145
graphs × 142
data-structures × 125
recurrence-relation × 102
loops × 85
recursion × 82
search-algorithms × 65
amortized-analysis × 61
correctness-proof × 54
randomized-algorithms × 51
big-o-notation × 45
approximation × 44
average-case × 42
quicksort × 41
arrays × 37
greedy-algorithms × 36
proof-techniques × 35
dynamic-programming × 33
probability-theory × 31