Questions tagged [algorithm-analysis]
Analyzing an algorithm to determine its time and space performance.
110 questions
13votes
3answers
1kviews
Trying to understand the 2N lnN compares for quicksort
I was going through the analysis of quicksort in Sedgewick's Algorithms book. He creates the following recurrence relation for number of compares in quicksort while sorting an array of N distinct ...
- 101
3votes
4answers
8kviews
Check distance between all elements in a list of numbers in O(n*lg(n))
I have an exercise for my algorithms and data structures class, where I basically have to implement a divide and conquer algorithm or function called check_distance to determine whether all numbers in ...
- 101
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 ...
- 218k
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 ...
- 11.9k
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") } }...
- 48.8k
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 ...
- 218k
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 ...
- 118k
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 ...
- 48.8k
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 ...
- 1,559
1vote
2answers
267views
More efficient alternative that checks if a list can be made a palindrome
For my algorithms and data structures class, I have to write an algorithm that is more efficient in the worst case than the following algorithm: def algo_X(A): i = 0 j = len(A)-1 while i &...
- 182
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)...
- 48.8k
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 ...
- 15.1k
3votes
1answer
417views
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 ...
- 3,167
