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.
1,948
questions
4
votes
1
answer
146
views
Warnsdorff's rule: more errors with odd sized boards
I wrote an algorithm based on the Warnsdorff's rule to solve the knight's tour problem, where you need to create a sequence of moves of a knight on a chessboard such that the knight visits every ...
- 167
1
vote
4
answers
101
views
Having a lot of trouble trying to reason the formal definition of Big O
My professor recently brushed over the formal definition of Big O:
To be completely honest even after him explaining it to a few different students we all seem to still not understand it at its core. ...
- 11
1
vote
1
answer
123
views
Shamos algorithm , cannot understand the Area part
I wanted to find shortest time algorithm for finding the diameter of a convex hull, so I found Shamos algorithm on wikipedia:
...
- 163
-2
votes
1
answer
49
views
Need the time complexity of this conditional statement method
My idea of the program is :
Input = n sets
objective function ObjFn equals to O(n^3)
Output = the order of n sets
Steps:
Applying ObjFn to all n sets
Choose the n of the Minimum ObjFn to be ordered ...
- 1
1
vote
1
answer
129
views
2
votes
1
answer
63
views
Why is this equality about the relative translation in the iterative closest point (ICP) algorithm obvious, and how can I derive it?
I'm a computer science bachelor student tasked with understanding On the ICP Algorithm by Esther Ezra, Micha Sharir, and Alon Efrat, and I'm having a lot of difficulty with even supposedly obvious ...
- 75
1
vote
2
answers
296
views
How can you have an upper and lower bound on the worst-case complexity of an algorithm?
Yesterday I started reading "An Introduction To The Analysis of Algorithms" by Sedgewick/Flajolet. For me it was not clear what he meant with "theory of algorithms" and the "...
- 21
1
vote
1
answer
134
views
Unstable nature of Lomuto partition scheme
In undergrad Quicksort implementation, Lomuto partitioning scheme is used. We are taught that Quicksort is an unstable partitioning algorithm which is cause of the extra swaps that occurs even when ...
- 21
1
vote
1
answer
79
views
2
votes
2
answers
466
views
Given n positive integers, pick two elements and subtract each by one with one operation. Find maximum number of operations
Problem Description: We have an array of $n$ positive integers and in one operation we have to choose two elements in the array and decrease them by $1$. (Elements on which we are performing this ...
- 21
2
votes
1
answer
112
views
Prove by induction $T(n) = T(\lfloor\frac{n}{2}\rfloor)+n^2 \in \Theta (\log_2 n)$
Text of the problem:
Solve the following recurrence equation and prove it by applying the principle of
induction:
$T(n) = \begin{cases} 3, \ n \le 2 \\ T(\lfloor\frac{n}{2}\rfloor)+n^2, \ n \ge 3 \...
- 143
2
votes
1
answer
190
views
What is the meaning of the statement "a sequence of n PUSH, POP and MULTIPOP opreations"
I am reading CLRS 3rd Ed, chapter 17.1 (Aggregate analysis pg453) and I came across this statement.
Let us analyze a sequence of n PUSH, POP, and MULTIPOP operations on an initially
empty stack.
I ...
- 65
4
votes
1
answer
404
views
Is there some kind of expected error margin for my Monte Carlo algorithm?
My Monte Carlo algorithm starts by placing some circles in the plane with potential overlaps. I then place a large circle somewhere and compute the overlapping area of this larger circle with the ...
- 665
1
vote
0
answers
104
views
Mistake in potential function for dynamic table contraction in CLRS?
In the third edition of "Introduction to Algorithms" by Cormen et al ("CLRS"), section 17.4 ("Dynamic tables") is an overview of amortized analysis as it relates to ...
- 11
0
votes
1
answer
71
views
How can we construct algorithm to evaluate logarithm of a real positive number
How can we construct the algorithm to evaluate the logarithm of a real positive number bit by bit in the base 2 system?
I have first expressed any number as $x\cdot2^n$, where $x \in [1,2]$, by ...
2
votes
1
answer
146
views
What is an O(n)-approximation?
I see the following notations used:
$O(1)$-approximation
$O(n)$-approximation
$\Omega(n)$-approximation
Can someone please explain what they mean?
I know what an approximation is with a normal ...
- 310
0
votes
1
answer
54
views
Considerations for space complexity analysis
There is a lot of information on time complexity analysis. For example, we know that for calculating the time complexity we study the number of operations (e.g. traversal, swapping, comparisons etc.) ...
- 337
0
votes
1
answer
93
views
Time Complexity Analysis When Merging Routes
I would like to know the best way to approach the time complexity analysis of the following algorithm. I have come up with 2 approaches so far.
We have a ...
1
vote
2
answers
124
views
Maximum flow in integer flow network
Let's say you have a maximum integer flow function in a network with 7 directed edges, meaning the flow cannot be increased anymore. The capacity of each edge is then increased by one. The capacity of ...
- 11
1
vote
1
answer
133
views
Traversing a directed graph with negative weights
Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...
- 115
2
votes
1
answer
136
views
best and worst case number of key comparisons of an algorithm
Consider the following algorithm:
...
- 1
0
votes
0
answers
31
views
Is there a Linear Transformer which uses only Matrix operations?
I am interested in finding a Linear Transformer which only uses ONLY matrix operations (more specifically matrix-matrix multiplications during training and matrix-vector multiplication in inference ...
- 137
1
vote
1
answer
30
views
Is the transformer SLiM compatible with ALBERT?
My question is about the article Sub-Linear Memory: How to Make Performers SLiM.
It is written in the article "our algorithm is compatible with distillation (Sanh et al., 2020)".
Now I would ...
- 137
2
votes
4
answers
693
views
Why was the fast inverse square root algorithm so ingenious?
In 2005 ID software open source the game Quake 3 Arena. When they did it was discovered was an algorithm that was so ingenious and all it did was calculate the inverse of a square root.
The easy way ...
- 135
0
votes
1
answer
123
views
Bin packing problem and optimality proof
Let $W$ be an array of weights. Store all the weights of $W$ in bins such that in each bin a heavier weight always go before a lighter weight (if $w_i\in W$ is stored before $w_j\in W$ then ...
- 115
0
votes
0
answers
19
views
Is it possible to run the transformer (performer) SLiM without using GPUs?
This question is about the article Sub-Linear Memory How to Make Performers SLiM.
I googled for the fastest transformer and I think almost surely I found. It is called SLiM.
The problem is the authors ...
- 137
0
votes
1
answer
41
views
prove sub array has a definite form with distinct end point integers
An array has elements from set {0, 1, 2}. A span SP of an array is any interval [start S, end E] such that the sub array must contain all elements from {0,1,2}.
For example: in Array A = (0,1,0,1,1,2,...
- 25
0
votes
1
answer
122
views
Return indices in the two sum problem
Given an array unsorted P of integers and a number m. I am trying to write a code that returns indices ...
- 138
1
vote
1
answer
82
views
How can I optimize the systems in the paper "Ensembling Ten Math Information Retrieval Systems"
My question is about the paper Ensembling Ten Math Information Retrieval Systems.
I already know the algorithms in the paper can answer questions only using dot products (look the post).
How can I ...
- 137
0
votes
1
answer
385
views
hash-tables - Expected-time for an unsuccessful search
The following question is from MIT-OCW 6.006, Spring-2008, Problem-Set 2, Q-3.c.
Suppose you have a hash table where the load-factor $\alpha$ is related to the number $n$ of elements in the table by ...
- 101
0
votes
1
answer
353
views
What could be the most efficient algorithm to find index in an array that matches given conditions?
I have an array A with n elements. I am trying to write an efficient algorithm to find the index of elements that matches condition A[j-1]>=A[j]<=A[j+1].
Example:
...
- 138
0
votes
1
answer
158
views
Inversions of Insertion Sort and Bubble Sort
An array with bubblesort time $\Theta(n)$ is nothing but a sorted array like:
A = 1 2 3 4 5
No swaps are done so only $n - 1$ comparisons.
An array with insertionsort run time $\Theta(n^2)$ is a ...
- 33
0
votes
2
answers
60
views
inversions in array
If the worst case arrays {5 4 3 2 1} have number of inversions as Θ(n^2) => n(n-1)/2 swaps
The best case arrays {1 2 3 4 5} have number of inversions 0(no swap)
What kind of arrays have number of ...
- 33
-1
votes
3
answers
82
views
sort is equal to inversions logic
In Bubble sort, the number of swaps/comparisons is equal to the number of inversions.
1st pass it will do (n -1) comparison
2nd pass it will do (n-2) comparison....so on
(n-1)n = n^2 - n
Worst case ...
- 33
0
votes
1
answer
34
views
simplified into asymptotic notation
I have a function that needs to be represented in theta form.
The below is my answer.
But the correct answer is 𝜃(n.2^n)
Can someone please explain me how??
- 33
1
vote
2
answers
140
views
Amortized Analysis of extract-min-operation of Fibonacci Heap
I am studying the operations of the Fibonacci heap. While going through min-extraction operation every step and its complexities are fairly clear to me. In short, it is:
The potential before ...
- 11
10
votes
2
answers
4k
views
Can I multiply Big-O time complexities?
Can I multiply Big-O time complexities?
For example: $O(n) \cdot O(n) = O(n^2)$?
UPDATE:
The question came from my observation that different sources analyze their algorithms in different ways. For ...
- 211
0
votes
0
answers
298
views
Analyzing Hybrid Merge and Insertion Sort
We know that merge sort takes O(n log n) and insertion sort takes (n^2) for worst case.
The combination of these two algorithm is to speed up and reduce key comparisons, as for a subarray with small ...
1
vote
1
answer
149
views
Prove that the following algorithm for division and remainders of natural numbers is correct
I am currently brand new to the correctness proof method, and have stumbled upon this algorithm which I find very tricky.
Prove that the following algorithm for division and remainders of natural ...
- 11
1
vote
1
answer
24
views
Complexity of checking graph separation
Let $G=(V,E)$ be an undirected graph and $A,B,C\subset V$ disjoint subsets of $V$. I want to check whether or not $A$ and $B$ are separated by $C$ (i.e. every path from $A$ to $B$ passes through $C$). ...
- 11
0
votes
1
answer
101
views
Differences between Polynomial and fully polynomial time approximation scheme
I have a confusion on understanding the relation between:
The input n
,The relative error and
The running time of the program In both PTAS and FPTAS.
In "The running time of PTAS must be ...
- 13
0
votes
1
answer
56
views
Polynomial and fully polynomial time approximation scheme
How to notice the type of algorithm whether it is polynomial or fully polynomial time approximation from the resulting running time ( execution time) of the program?
Is there any other way to decide?
- 13
1
vote
2
answers
66
views
Why is the time complexity of the Bit Manipulation solution to Binary Addition O(M + N)?
I am trying to understand why the time complexity of the Bit Manipulation solution (https://leetcode.com/problems/add-binary/solution/) to the Binary Addition problem is O(M + N), where M and N are ...
- 125
0
votes
2
answers
83
views
How do you justify making algorithm subroutines more efficient when Big-O notation only includes the dominant term?
I don't really understand time complexity, and wanted some clarification in this hypothetical situation.
If I were being given items one by one, and I wanted a list of them all in the reverse order I ...
- 103
3
votes
0
answers
77
views
Running time analysis of Savitch's algorithm
Savitch provided an algorithm which places NL in L^2 and hence the runtime of the algorithm is bound by $2^{O(\log^2n)}$. The runtime of the algorithm is not in P as NL is not known to be in SC.
Is ...
0
votes
1
answer
48
views
Need help understanding tightest lower bound ( BigOmega ) of n!
I am currently learning complexity theory and wasn't able to find a tightest lower bound to BigOmega(n!), I am quite certain it isn't n^n and so wasn't able to reach to a tightest lower bound, can log(...
- 219
2
votes
1
answer
66
views
Ask for help to prove a inequality, thanks
Can anyone help to prove that
$\sum\limits_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right) > cn$ for some constant $c>0$?
Here $k=\Big[\frac{n}{2\log_2 n}\Big]$ and $[x]$ denotes the integer ...
- 21
-1
votes
1
answer
57
views
Why 2^(2n+2) not equal to θ(2^2n)?
I'm trying to prove this expression 2^(2n+2) ≠ θ(2^2n)?
Firstly 0 <= c1.2^(2n) <= 2^(2n+2) for this n=1 c1=1 is a solution set.
For n = ∞, 0 <= ∞.c1 <= ∞ c1=1 is provide it. So omega ...
- 1
2
votes
1
answer
249
views
Counting primitive operations on recursive functions
I'm reading Algorithm Design and Applications, by Michael T. Goodrich and Roberto Tamassia, published by Wiley. They teach the concept of primitive operations and how to count then in a given ...
- 135
2
votes
1
answer
374
views
Understanding the upper bound proof for quick sort
I'm trying to understand the average run time of quicksort which is $O(n \log n)$.
I understand the intuition behind it: if we partition array $A$ to e.g. $\alpha n $ and $(1-\alpha)n$ then we ...
- 123