The algorithm-analysis tag has no wiki summary.
1
vote
4answers
258 views
Approach to simplifying an algorithm
For completely random reasons*, I wrote some code that calculates and displays the following expression:
P=1*(2+2)(3+3+3)(4+4+4+4)..(n+n...…
Which is equivalent to (n!)^2
The version I wrote ...
5
votes
6answers
486 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 ...
6
votes
1answer
162 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 ...
0
votes
2answers
200 views
Does this version of insertion sort have O(n) complexity for best case?
for ( i = 1 ; i <= N ; i++ )
{
for ( j = 0 ; j < i ; j++ )
{
if ( arr[j] > arr[i] )
{
temp = arr[j] ;
arr[j] = arr[i] ;
for ( k = i ; k > j ; k-- )
...
5
votes
5answers
604 views
Why interviewers want Optimal Algorithms
In an interview with a software company they asked me some algorithm design questions.
Being strong in mathematics I was able to solve it mathematically, but each time when I propose my algorithm ...
3
votes
1answer
280 views
A* Algorithm Completeness Proof
The A* Algorithm is the optimal (provided the heuristic function is underestimated), complete & admissible (provided some conditions). I know the proofs of admissibility & optimality.
But how ...
1
vote
0answers
84 views
How to compute amoritized cost for a dynamic array?
I am trying to understand how to do the amortized cost for a dynamic table. Suppose we are using the accounting method.
Let A of size m be an array of n elements. When n = m, then we create a new ...
2
votes
1answer
155 views
How much times command executed? Looking for mistake
I have following piece of code:
int sum = 0;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
for (int k = 1; k <= N; k = k*2)
for (int h = 1; h <= k; ...
1
vote
3answers
396 views
finding the time complexity of the following program
I need to find the time complexity in terms of Big Oh notation for the following program which computes the factorial of a given number: The program goes like this:
public int fact(int n){
if (n ...
0
votes
1answer
141 views
Sublinear Extra Space MergeSort
I am reviewing basic algorithms from a book called Algorithms by Robert Sedgewick, and I came across a problem in MergeSort that I am, sad to say, having difficulty solving. The problem is below:
...
0
votes
1answer
132 views
Help with algorithmic complexity in custom merge sort implementation
I've got an implementation of the merge sort in C++ using a custom doubly linked list. I'm coming up with a big O complexity of n^2, based on the merge_sort() > slice operation. But, from what I've ...
1
vote
1answer
203 views
How should I compress a file with multiple bytes that are the same with Huffman coding?
On my great quest for compressing/decompressing files with a Java implementation of Huffman coding (http://en.wikipedia.org/wiki/Huffman_coding) for a school assignment, I am now at the point of ...
2
votes
4answers
271 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:
...
1
vote
2answers
165 views
need explanation on amortization in algorithm
I am a learning algorithm analysis and came across a analysis tool for understanding the running time of an algorithm with widely varying performance which is called as amortization.
The autor quotes ...
1
vote
1answer
113 views
Does it matter the direction of a Huffman's tree child node?
So, I'm on my quest about creating a Java implementation of Huffman's algorithm for compressing/decompressing files (as you might know, ever since Why create a Huffman tree per character instead of a ...
