Questions tagged [algorithm-analysis]
Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage. Use the [runtime-analysis] tag for questions about the runtime of algorithms.
2,051 questions
1
vote
1
answer
66
views
Big O and Omega, how can they be different for a specific case(worst/best)
So I understand that O is an upper bound and omega is a lower bound. I also understand that case is different than bounds, i.e worst case can have O/Theta/Omega different from best case.
My question: ...
- 11
0
votes
1
answer
94
views
Is there an algorithm whose worst-case time complexity is not describable by Big-Theta?
I understand the definitions of Big-O (upper bound), Big-Ω (lower bound), and Big-Θ (tight bound), particularly when it comes to its use to finding the complexity of given growth function such as f(n) ...
- 3
3
votes
1
answer
152
views
Interesting pattern in $k$-ary search
I was playing around with $k$-ary searches, and found something interesting:
This is the $\log(\frac{\text{time}}{\text{binary time}})$ to find an element in an array of length $100$ averaged over ...
- 81
1
vote
1
answer
160
views
How fast can cyclic shift be implemented?
How fast can cyclic shift of size $n$ be implemented? Lets say the input is a string of length $n+ \log_2 n$ where the last $\log_2 n$ tell the function how much to shift the first n digits.
I know ...
- 155
0
votes
1
answer
64
views
Does Reversing a Directed Acyclic Graph and Performing Post-Order Traversal Yield a Valid Topological Sort?
Reversing the post-order traversal (DFS) of a directed acyclic graph (DAG) results in a valid topological sort.
However, if we first reverse the graph (where every directed edge from ( u ) to ( v ) ...
- 121
2
votes
1
answer
72
views
How many times is Decrease-Key called per edge in Prim's algorithm?
This is how I understand Prim's algorithm:
Initialization: When Prim's algorithm starts, it initializes the priority queue with all vertices, setting their keys (distances) to infinity, except for the ...
- 121
4
votes
0
answers
75
views
Remove contiguous 5th powers (5-fold repetitions) from list of 'a's and 'b's?
Given a list of characters in $\{a,b\}$, for example $abababababa$, what is the most efficient way to remove all 5th powers in a way that makes the string as short as possible?
(This example would ...
- 141
1
vote
1
answer
64
views
AC-3 algorithm and requeueing
I'm watching CS50AI's week 3 video, particularly the part describing the AC-3 algorithm, which starts at around 1h 10m. I'll paraphrase the algorithm
...
- 111
1
vote
2
answers
170
views
Is it possible to compare the equivalence of two logical expressions in sub-exponential time?
Let us say that $\text{Bool}$ is the set of possible boolean values; that is, $\text{Bool}=\{\text{True}, \text{False}\}$. Assume we have two functions $f$ and $g$ that are both $\text{Bool}^n\...
- 111
1
vote
0
answers
40
views
Leader Election: A question about Peterson's Improved Algorithm for Unidirectional Ring
This question refers to Peterson’s improved election algorithm for unidirectional ring:
...
1
vote
2
answers
154
views
How to prove $T(n) = 2T(\lfloor\frac{n}{2}\rfloor) + n$ is $\Omega(n\log n)$?
I know how to prove for $O(n\log n)$, but I'm hitting a roadblock with this one. Here's what I've tried:
The hypothesis is that there exists some $c > 0$ so that $T(n) \geq cn \log n $, by assuming ...
- 11
0
votes
1
answer
93
views
Comparing Two Adjacency Matrices for Graph Equality
I'm currently working on a project that partially involves graphs. One of the problems I'm tackling is determining whether two given matrices represent the same graph.
So given two different adjacency ...
- 47
2
votes
1
answer
164
views
Comparison of time complexity for NFA and backtracking implementations of regex search
I followed this helpful blog "Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)" by Russ Cox. This link is got from Russ Cox, ...
- 233
3
votes
1
answer
121
views
Show that both the standard and bottom-up greedy strategies give the same outcomes
Suppose there are $n$ players $N = \{p_1, \cdots, p_n\}$ and a set $M$ of $m \geq n$ items that are to be claimed. Suppose further that players have strict, additive, ordinal rankings $\succ_{p_j}$ ...
- 108
2
votes
0
answers
53
views
Asymptotic complexity of knapsack algorithm considering all numbers ∈ Z
In the knapsack problem, we consider numbers ∈ Z+ which gives us a run time of $O(nW)$. To my understanding, this is pseudo-polynomial and the worse case runtime is $O(n*2^{log(w)})$
My question is, ...
- 21