Questions tagged [algorithm-analysis]
Analyzing an algorithm to determine its time and space performance.
110 questions
2votes
7answers
4kviews
Why is big O notation an asymptotic notation/analysis?
An asymptote in mathematics represents a value (line) to which the observed function constantly approaches. In other words, as the value of X increases towards infinity, i.e. decreases towards minus ...
- 147
3votes
1answer
310views
Algorithms: How do I sum O(n) and O(mlog(n)) together?
I'm doing a running time analysis using the aggregate method and I'm a bit confused about what would be the result in this case. I have some intuition in inferring that it would be O(mlog(n)) but I'm ...
- 51
1vote
1answer
115views
Some questions about shortest-path algorithms
I'm trying to understand why anyone would prefer Floyd-Warshal over Dijkstra: Dijkstra gives a correct result, using an understandable system, combined with backtracking. Floyd-Warshal makes an ...
- 1,846
1vote
3answers
190views
How can I mix this grid to guarantee it being solvable in X minimum steps?
Note: This question is not about this particular instance of this grid with these exact words, but about any combination of words. I am programming a puzzle game where you have to arrange a grid of ...
0votes
2answers
363views
fastest way to find number of smaller elements to the right of an array
In Daily Coding Problem, Miller&Wu have the following problem : Given an array of integers, return a new array where each element in the new array is number of smaller elements to the right of ...
- 181
4votes
1answer
1kviews
What is the most suitable data structure for IPv4 addresses with intersecting ranges?
Mostly in all routers and operating systems the Longest Prefix Match algorithm is used for searching the trie of IPv4 addresses. Packet filters like Iptables don't need some special data structure for ...
- 99
0votes
1answer
1kviews
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 ...
0votes
2answers
1kviews
Calculating time complexity of a code snippet
I am trying to calculate the time complexity of the below code snippet def func() { for(i=1; i<=n; i++) { for(j=1; j<=n; j=j+i) { print("hello") } }...
- 111
5votes
4answers
641views
Processing a 2D matrix - need to speed up my O(n^4) algorithm
I have an n x n matrix which I need to convert into a list sorted by value. Starting with the maximum value cell at (row x1, col y1), I must immediately exclude all cells where (x >= x1, y <= y1)...
- 187
1vote
2answers
146views
Does a microcontroller provide better accuracy for comparing algorithms' run-times?
I have a set of algorithms to choose from based on their execution speed. I know that it is very hard to get an accurate measurement due to the process scheduling, the time that is actually consumed ...
- 141
3votes
1answer
416views
Why the names Omega and Theta in Big Omega and Big Theta?
There was a question asking what the "O" stands for in "Big O", the answer to which seems to be "Ordnung von"/"order of". I wonder what's the origin of the ...
- 791
2votes
1answer
587views
Running time for simple for loops - Big O notation
I am currently doing some exercises with algorithms and I find myself in a huge problem. It seems that everybody understands this type of problem but I have a really hard time figuring it out. For ...
21votes
6answers
5kviews
Using a different algorithm depending on the size of the input
I recently finished a course on advanced algorithms, and another on complexity & computability theory, and in the past few days my mind has been somewhat preoccupied by this question. Why don't we ...
- 345
4votes
2answers
294views
How can I know when a paper is too hard for me to be able to implement their code and/or understand their math - within a given deadline?
I've been assigned to explore implementing (along with modifications, so understanding it is a must) this algorithm for the 'Redistricting Problem': https://dl.acm.org/doi/pdf/10.1145/3274895.3274979 ....
1vote
0answers
209views
Rectangle packing / Bin packing with multiple frames
I have multiple rectangular frames, with different fixed heights. The width should be minimized and there is a maximum width. Then there are many different smaller rectangles. These should be packed ...
