Questions tagged [algorithm-analysis]
Analyzing an algorithm to determine its time and space performance.
112 questions
9 votes
9 answers
3k views
How to choose between brute force and efficient solution that has overhead?
Using Big O notation, it is clear that I should go with the more efficient approach, but I know that there is a significant cost in terms of initialization for more efficient solutions. The Problem: ...
- 111
2 votes
7 answers
4k views
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
1 vote
1 answer
130 views
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,844
0 votes
2 answers
395 views
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
0 votes
1 answer
1k 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 ...
- 103
5 votes
4 answers
684 views
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
3 votes
1 answer
436 views
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
21 votes
6 answers
5k views
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