The algorithm-analysis tag has no wiki summary.
3
votes
3answers
421 views
Why Big Data Needs To Be Functional?
I started working on a new project lately related to Big Data for my internship.
My managers recommended to start learning functional programming (They highly recommended Scala).
I had a humbled ...
0
votes
0answers
73 views
Single / Multi Pattern Algorithms
I have been reading, that Knuth-Morris-Pratt was not a very good algorithm, although used in specific cases, but I haven't been able to find one "real" case.
Does anyone know one specific case in ...
1
vote
1answer
93 views
How to calculate the worst-case runtime of this search-algorithm
I've written a special indexOf function for a list of unsorted unique values.
I can search for one or multiple (unsorted) values, passed as array/list, and the function will return me an array/list ...
0
votes
0answers
48 views
I've written remainder(x,y) in OCaml. Is there more efficient than O(n)? [migrated]
Here's my code:
let rem x y =
let rec aux acc i n =
if i=n then acc else
if acc+1=y then aux 0 (i+1) n else
aux (acc+1) (i+1) n in
aux 0 0 x;;
I'm just learning OCaml and I wonder ...
-4
votes
1answer
209 views
What is the big-O cpu time of Euclid's Algorithm of “Greatest common divisor of two numbers”
Looking at Euclid's algorithm for the "Greatest common divisor of two numbers", I'm trying to divine the big-O cpu time for numbers K, and N. Can anybody help?
This is the algorithm as I understand ...
5
votes
2answers
254 views
difference between accounting and potential methods in Amortized Analysis
I was going through the Introduction to Algorithms by Cormen et al.In the chapter titled Amortized Analysis,the difference between accounting and potential methods is given like this
The ...
6
votes
1answer
146 views
Bin sorting problem - Please help categorize
I have a problem I am developing a solution for and currently I solve it with a brute force solution that checks all possibilities. It works for small numbers of bins but I'd like to work with a ...
13
votes
2answers
433 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 ...
6
votes
6answers
2k 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 ...
0
votes
1answer
43 views
clarification about amortized analysis
I was going through an article here
In the section named Aggregate Method ,the author says
Then summing over the entire sequence, all the 1's sum to O(n), and all the di also sum to O(n). That ...
2
votes
1answer
160 views
Algorithm in undirected BFS graph
I'm trying to put together an algorithm that will display the node degree for every node in a breadth first tree graph (assume BFS was called). Assume it's an undirected graph. I'm not sure how to ...
1
vote
1answer
582 views
Matrix Pattern Recognition Algorithm for a 2D space
I have a picture that I elaborate with my program to obtain a list of coordinates.
There is a matrix represented in the image.
In an ideal test I would get only the sixteen central points of each ...
5
votes
4answers
307 views
Find the peak of each islands in sparse matrix
I have a sparse matrix that contains several islands of unknown size. I would like to find the highest peak of each islands. Consider this matrix as an example:
0 0 1 0 0 0 0
0 0 1 2 1 0 0
0 0 0 3 2 ...
0
votes
1answer
256 views
Priority queue for Kruskal's algorithm with running time O(E lg V)
I'm reviewing my notes on Kruskal's algorithm and have a question about getting the runtime down to O(E lg V). By using a PQ with edges and a boolean array of which vertices we have added to our tree ...
20
votes
3answers
2k 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 ...
2
votes
4answers
306 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
600 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 ...
7
votes
1answer
495 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
368 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
646 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
551 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 ...
2
votes
1answer
162 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
165 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
2k 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 ...
1
vote
1answer
270 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
153 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
328 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
407 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
178 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
141 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 ...
2
votes
1answer
306 views
Why create a Huffman tree per character instead of a Node?
For a school assignment we're supposed to make a Java implementation of a compressor/decompresser using Huffman's algorithm.
I've been reading a bit about it, specially this C++ tutorial: ...
10
votes
7answers
2k 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 ...
