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
-3
votes
1
answer
94
views
Algorithm Discovery Using ChatGPT O3-mini-high?
I gave this prompt to ChatGPT o3-mini-high: Give me a novel algorithm not discovered yet that reduces the complexity of matrix multiplication. Do you think this algorithm is correct and truly novel?
...
- 9
1
vote
1
answer
77
views
Find rank of vector of length $k$ with elements up to $n$ in graded lexicographic order (grlex)
Let $v = (a_1, a_2, …, a_k)$ be a vector of length $k$, such that $0 \leq a_i < n$. Also let $|v| = a_1 + a_2 + \dots + a_k$ be a total degree of $v$. There is finite number of such vectors.
We can ...
- 133
2
votes
1
answer
113
views
Approximation algorithm for a problem similar to load balancing
This's exercise $7$ of chp $11$ from the popular book algorithm design by Jon and Eva. It's about designing a $2$-approximation algorithm for a problem similar to Load balancing on parallel machine. ...
- 225
2
votes
1
answer
122
views
Sorting: worst-case time complexity best upper bound (Challenge)
Assuming a model of like multitape TM, (meaning do not assume O(1) time for operations or anything). Informally, what is the best known algorithm worstcase-wise (as a function of the input) for ...
- 123
1
vote
0
answers
47
views
How to determine the time complexity of the Local Search Algorithm in this paper?
I am trying to estimate the theoretical time complexity of the Local Search algorithm presented in the paper "Virtual Resource Allocation for Mobile Edge Computing: A Hypergraph Matching Approach&...
0
votes
1
answer
74
views
How to prove $n!$ is $o(n^n)$ without limits? (only by the definition of little o)?
I'm a bit stuck with this problem? So far all I could do is write out and expand $n!$ as well as $n^n$. Move both to the same side and see that $n^n$ gives a limit (as n goes towards infinity) that ...
2
votes
1
answer
73
views
What is the loop invariant for stack-based algorithm for finding largest rectangle enclosed in a histogram?
I would like some help with proving the correctness of the following algorithm that solves LeetCode problem 84 of finding the largest rectangle enclosed by the bars of a histogram. For simplicity, we ...
- 45
0
votes
1
answer
120
views
how to find a recurrence relation given a piece of code
I have this piece of code and I have to find the recurrence relation in function of n. The problem states that the algorithm is initially called with ALGO(A, 1, n). A is an array of size n. The ...
- 11
0
votes
1
answer
104
views
0
votes
1
answer
159
views
Any better algorithm compared to continuous fractions for solving Pell Equation?
Pell equation : x^2 - ny^2 = 1
Solving it with continuous fractions is well known, such as following code:
...
- 21
-1
votes
4
answers
267
views
Space Complexity of Merge Sort
What is the specific space complexity of the Merge Sort algorithm, as partially implemented below?
...
- 13
1
vote
1
answer
101
views
Finding a function $\hat{\mu}:[0,1]\to\{0,1\}$ for a data set $X_i:[0,1]\to\{0,1\}$ that minimizes the sum of squared distances to that function
Not long ago I requested an algorithm that can find the word minimizing the sum of squared Hamming distance of all words in a data set. The answer to this question is that the minimization problem is ...
- 143
0
votes
0
answers
96
views
Forward-Edge-Only Algorithm
I came across this interesting theoretical CS problem regarding max-flow networks in Algorithm Design (Kleinberg Tardos 2005):
The Forward-Edge-Only algorithm, which finds $s-t$ paths using only ...
- 1
0
votes
0
answers
64
views
Measuring logicality of programming languages?
I have a simple question of how would you measure the logicality of a programming language?
EDIT: I was asked to specify the term "logicality". Hence I will try and provide a stipulation. By ...
- 11
0
votes
1
answer
111
views
Complexity of peak finding algorithm for N dimensions
I am totally new in this area.
Lets say we have a list of random numbers and we have to find one peak value (only one is fine), and a peak is if $a \geq$ than its both neighbours (or one if it is in ...
- 103
0
votes
1
answer
79
views
Time Complexity of Backtracking solution to Leetcode 473. Matchsticks to Square
The following is a Leetcode problem: 473. Matchsticks to Square (https://leetcode.com/problems/matchsticks-to-square/description/)
Problem Statement
You have an array, matchsticks, of size n, with ...
- 1
3
votes
1
answer
233
views
Worst-case analysis of Brent's cycle algorithm
I've been reading Brent's original paper and struggling with his worst-case bounds derivation. (I won't even bother with the expected behavior analysis.) I get the Floyd's algorithm analysis as that's ...
- 630
0
votes
1
answer
69
views
Algorithm Analysis Help
I would like help understanding this slide from my class, especially the inner loop part. I do not understand how he is getting at n - (n - 1 - 1) = 2
I do understand that when j = n - 1 we get n - (n ...
user169539
3
votes
1
answer
147
views
When is an algorithm "equal" to another?
I have two algorithms $P, Q$ for solving the same problem (a decision problem on sequences in $R^n$) and I want to decide if they differ in any meaningful way. The following describes the constraints:
...
3
votes
1
answer
228
views
Minimize sum of array after repeated replacement of numbers with their OR operation result
I participated in an algorithms contest recently, and couldn't find an answer to this problem.
The contest is over now, and am looking to see if someone might know how to solve this.
Question:
"...
- 340
3
votes
3
answers
521
views
Proof of correctness for optimal solution for sorted two-sum
I have been solving the problem of two sum with a sorted array, which can described as follows:
Given a sorted array arr sorted in non-decreasing order and a ...
- 133
2
votes
1
answer
122
views
Proof for Gas Refills on Circular Route Problem
The circular route gas station problem asks: If given a car with an unlimited gas tank, find the gas station on a circular road that if started from would allow you to travel station to station ...
- 23
1
vote
2
answers
99
views
What does "computer steps" mean in this runtime definition?
My algorithms textbook defines $T(n)$ as "the number of computer steps needed to compute fib1(n)" (where fib1(n) ...
- 111
0
votes
1
answer
53
views
Is repeated function evaluation constant-time if the function is defined by the entry?
In an algorithm, given a natural number $n$, i have to calculate all integer entries of a function $f_n:R_n\to\mathbb{R}$ within an interval $R_n=[a,b]$ in the real line. Clearly, this amounts to ...
0
votes
0
answers
132
views
Closed-form for exact number of iterations of binary search
Consider a sorted list of $n$ elements $x_1, \ldots, x_n$. Using binary search to find $x_k$ in this list takes $f(n, k)$ iterations, where $f : \mathbb{N}^2 \to \mathbb{N}$ is a function such that, ...
- 103
0
votes
2
answers
1k
views
How to count primitive Operations
I've been struggling with counting primitive operations. I know that you do not have to outline every operation that happens in your pseudocode but this is never the less a bit complicated for me. ...
- 9
1
vote
1
answer
99
views
Algorithms by Dasgupta-Papadimitriou-Vazirani Prologue confusion
We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly
proportional to n; this is not too hard to understand if you think back to the gradeschool procedure for addition, ...
- 111
0
votes
1
answer
59
views
Why is it impossible to do a linear time radix sort on n integers and ranging from $0$ to $n^{3} - 1$?
I propose by doing a base-n expansion of the numbers, we have that since there are $n^{3}$ values and $n$ digits in this expansion, there are a total of $\log_{n} n^{3} = 3$ digits. Note in this base-...
- 103
0
votes
1
answer
60
views
Set partitions and integer partitions
Consider an algorithm that takes the input a finite set $X$ and an integer partition $\sum_{i=1}^k n_i=|X|$ and gives output all the set partitions $\left(S_1,\ldots, S_k\right)$ of $S$ satisfying $|...
- 101
0
votes
1
answer
113
views
How far can we push "counting argument" for proving lower bounds of time complexity?
It's obvious that we cannot find min (or max) in an array of length n in strictly less than n "steps". It's also well-...
0
votes
1
answer
60
views
Is this depth search correct (DFS) Shouldn't one act according to the LIFO principle?
Shouldn't we actually continue with C after A, thought a depth search, follows the LIFO principle, isn't C the last node added in this case and shouldn't we expand C before B?
- 1
-2
votes
1
answer
68
views
Proving a statement involving asymptotic notation
I need help with this question. If it’s possible to do this without limits, please show. Thanks.
Q: If f(n) is Ω(n) and g(n) is O(n), then prove or disprove the following statement: f(n) is O(n)
- 1
7
votes
1
answer
652
views
Possible Mistake in Skiena's Algorithm Design Manual
In Skiena's book Algorithm Design Manual, 3rd Edition, it is claimed on page 45 that
$$
mn - m^2 + m \in \Omega(mn)
$$
where $m,n \geq 0$ and $m \leq n$. I claim that this is in fact false, with the ...
- 173
2
votes
0
answers
161
views
Find the longest northeast path in $O(n\log n)$ time
Given a set $Z$ of $n$ points $(p_1,p_2,p_3, \ldots,p_n)$. The coordinates of these points are arbitrary numbers and are unsorted. If they give me $s$ and $t$ to be two points in $Z$. A northeast path ...
- 121
1
vote
1
answer
248
views
Quick sort with $K-1$ pivots
I was thinking about quicksort with multiple pivots and I came across this question. How can we efficiently implement a version of Quicksort where we choose $k−1$ pivots to partition an array of ...
- 13