Questions tagged [algorithm-analysis]
Analyzing an algorithm to determine its time and space performance.
112 questions
34
votes
5
answers
16k
views
Divide and Conquer algorithms – Why not split in more parts than two?
In divide and conquer algorithms such as quicksort and mergesort, the input is usually (at least in introductory texts) split in two, and the two smaller data sets are then dealt with recursively. It ...
- 1,012
32
votes
5
answers
49k
views
Algorithms: How do I sum O(n) and O(nlog(n)) together?
I have the follow algorithm which finds duplicates and removes them:
public static int numDuplicatesB(int[] arr) {
Sort.mergesort(arr);
int numDups = 0;
for (int i = 1; i < arr.length; ...
23
votes
4
answers
4k
views
When speaking, how can I say that the time complexity order of an algorithm is O(N log N)?
What term can I use to describe something with O(N log N) complexity?
For example:
O(1): Constant
O(log N): Logarithmic
O(N): Linear
O(N log N): ??????
O(N2): Quadratic
O(N3): Cubic
- 385
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
20
votes
8
answers
28k
views
Why is binary search,which needs sorted data, considered better than linear search?
I have always heard that linear search is a naive approach and binary search is better than it in performance due to better asymptotic complexity. But I never understood why is it better than linear ...
- 3,044
15
votes
2
answers
9k
views
Time complexity of 2^sqrt(n)
I am solving an algorithm question and my analysis is that it would run on O(2^sqrt(n)). How big is that? Does it equate to O(2^n)? Is it still non-polynomial time?
- 261
13
votes
7
answers
8k
views
Big Oh notation does not mention constant value
I am a programmer and have just started reading Algorithms. I am not completely convinced with the notations namely Bog Oh, Big Omega and Big Theta. The reason is by definition of Big Oh, it states ...
- 313
13
votes
3
answers
1k
views
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 ...
- 299
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
8
votes
5
answers
18k
views
How to discriminate from two nodes with identical frequencies in a Huffman's tree?
Still on my quest to compress/decompress files with a Java implementation of Huffman's coding (http://en.wikipedia.org/wiki/Huffman_coding) for a school assignment.
From the Wikipedia page, I quote:
...
- 3,937
8
votes
1
answer
2k
views
Possible Damerau-Levenshtein improvement?
I recently implemented the Damerau-Levenshtein distance algorithm from the pseudocode on Wikipedia. I couldn't find any explanation of exactly how it works and the pseudocode uses completely ...
- 348
7
votes
3
answers
15k
views
Is O(log n) + O(log n) = O(n)? [duplicate]
We know that binary search takes O(log n) in Big O notation but if we need to run twice an algorithm of O(log n), would it be the same as O(n) in time complexity?
For example, if I have a method to ...
- 181
7
votes
2
answers
4k
views
Space complexity of Iterative Deepening DFS
We read on Wikipedia > Iterative deepening depth-first search that
The space complexity of IDDFS is O(bd), where b is the branching factor and d is the depth of shallowest goal.
Wikipedia also gives ...
- 597
6
votes
8
answers
3k
views
How meaningful is the Big-O time complexity of an algorithm?
Programmers often talk about the time complexity of an algorithm, e.g. O(log n) or O(n^2).
Time complexity classifications are made as the input size goes to infinity, but ironically infinite input ...
- 191
6
votes
3
answers
4k
views
Effecient algorithm for data deduplication in procedural code
I have written a data cleansing application which, for the most part, works well. It is not designed to handle large volumes of data: nothing more than about half a million rows. So early on in the ...
- 3,646