The algorithm-analysis tag has no usage guidance.
27
votes
5answers
4k 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 ...
19
votes
4answers
3k 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
16
votes
5answers
6k 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; ...
13
votes
2answers
529 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 ...
11
votes
7answers
4k 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 ...
9
votes
7answers
9k 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 ...
8
votes
3answers
4k 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 ...
8
votes
1answer
991 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 ...
6
votes
2answers
1k 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 ...
5
votes
5answers
697 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 ...
5
votes
3answers
298 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 ...
5
votes
4answers
832 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 ...
5
votes
1answer
592 views
Compute Adjacent Pair
I was given the following problem:
Integer V lies strictly between integers U and W if U < V < W or if U > V > W.
A non-empty zero-indexed array A consisting of N integers is given.
A ...
5
votes
2answers
1k 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 ...
5
votes
1answer
254 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 ...
4
votes
8answers
1k 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 ...
4
votes
2answers
484 views
Loop runtime question
I had an exam today and I feel that I did pretty well, except I could not for the life of me figure out what appears to be an unbelievably simple question.
We were asked to give theta notation run ...
4
votes
3answers
149 views
Algorithm Analysis: In practice, do coefficients of higher order terms matter?
Consider an^2 + bn + c. I understand that for large n, bn and c become insignificant.
I also understand that for large n, the differences between 2n^2 and n^2 are pretty insignificant compared to the ...
3
votes
1answer
1k 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 ...
3
votes
4answers
1k 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
votes
1answer
225 views
Sentence Tree v/s Words List
I was recently tasked with building a Name Entity Recognizer as part of a project. The objective was to parse a given sentence and come up with all the possible combinations of the entities.
One ...
3
votes
2answers
124 views
Big O Nested For Loop Breakdown
I understand how to get a general picture of the big O of a nested loop, but what would be the operations for each loop in a nested for loop?
If we have:
for(int i=0; i<n; i++)
{
for(int ...
3
votes
1answer
594 views
How this Fibonacci exponentiation by squaring algorithm works?
This is one of the best algorithms to calculate the nth Fibonacci sequence. it needs O(log(n)) time to do its job, so it's so efficient. I found it somewhere but don't know how it works!
Can anyone ...
2
votes
4answers
378 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 ...
2
votes
3answers
231 views
Close to knapsack problem?
I think that I am trying to solve a problem somewhat similar to a knapsack problem. I am not sure though.
Please see the input given below and my solution. There are three types of items and 4 ...
2
votes
2answers
172 views
Estimating run time of algorithm
For instance if i have an algorithm that is O(n2) and it will run for 10 seconds for a problem size of 1000. Now if i were to double the problem size to 2000 i want to know the approximate run time in ...
2
votes
1answer
274 views
Asymptotic running time of for-loops
I have this question which I need answered:
What is the asymptotic running time for the following piece of code?
if (N < 1000)
for (int i = 0; i < N; i++)
for (int j = 0; j < N; ...
2
votes
3answers
93 views
recalculation model for GUIs
I often come across this problem.
Say to have a form with some controls:
A
B
C = A + B
D
E = C * 2 ONLY IF D==TRUE
F
G = A - F
The user fills A, then B.
The system calculates C.
The user fills D ...
2
votes
1answer
527 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:
...
2
votes
1answer
348 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: ...
2
votes
1answer
49 views
What is the order analysis of the following (using a list of primes)
I have the following program:
Iterate x from 1 to N. Check to see if x is prime. If it is, add it to a list of primes.
The way I check to see if it is prime is iterating through the current list ...
2
votes
1answer
221 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 ...
2
votes
1answer
265 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
192 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
2answers
338 views
How to approach program design with respect to data strucutres and algorimths - is there an equivelant of the OO design process for d.s.'s + algs? [closed]
My applogies for probably the worst written body of text I have produced in my life and many thanks to those willing to plough through it all.
I was (and still am) not able to clearly express what I ...
1
vote
4answers
454 views
How to trace logical errors in algorithms [closed]
I am beginner in algorithms. Last year I participated in Google Code Jam. One of the major issues I faced during the competition was my code was working fine on my test cases, but when I submitted on ...
1
vote
1answer
654 views
Calculate Big-O for nested for loops
I found this nested loop to calculate the Big-O notation.
for(i=0;i<n;i++)
for(j=0;j<i*i;j++)
for(k=0;k<j;k++)
I got the time complexity for the algorithm with this polynomial ...
1
vote
1answer
159 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 ...
1
vote
2answers
119 views
What's the professional name for the software planning diagrams, those with ellipses and rhombuses?
What's the official name for a diagram like this one, used to structure a conditional plan.
The shapes of the objects are by convention ellipse for an action, rhombus for a question, rectangle for a ...
1
vote
2answers
292 views
Is the time complexity of a while loop with three pointers different than 3 nested for loops?
This program (written in ruby) finds the largest 3 numbers in an array (without sorting the array). It has a while loop with three pointers. My fist instinct, since there is only one loop is to say ...
1
vote
2answers
664 views
Lower and Upper bound of an algorithm
I am learning about analysis of algorithms.
I came across the term "upper bound" and "lower bound" in "worst-case" running time of an algorithm.
Are they applicable to only the "worst case" or can ...
1
vote
2answers
275 views
How to measure algorithm accuracy?
I have a few optimization algorithms (for finding function minimum) and I'd like to check how good they are. Suppose I build test cases and compare the actual results to theoretical ones.
What ...
1
vote
2answers
367 views
Given two sorted array in ascending order with same length N, calculate the Kth min a[i]+b[j]. Time complexity O(N)
Given two sorted array in ascending order with same length N, calculate the Kth min a[i]+b[j]. Time complexity O(N).
Another variant of the question goes like this:
given a matrix with sorted rows, ...
1
vote
2answers
164 views
What is the algorithmic time complexity of this program?
I wrote a simple program in java to create and maintain Dynamic Arrays:
public class DynamicArrays {
private Integer[] input = new Integer[1];
private Integer length = 0;
private Integer ...
1
vote
1answer
145 views
Big O notation of randomness
I was thinking about inefficient algorithms based on randomness and wondered how to categorise them.
For instance. Say you wanted to generate all the numbers from 1 to N in a random order but only ...
1
vote
3answers
290 views
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 ...
1
vote
1answer
1k 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 ...
1
vote
1answer
548 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 ...
1
vote
2answers
196 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
103 views
More efficient alternative that checks if a list can be made a palindrome
I asked this question on Stackoverflow, but they told me this is the best place to ask.
For my algorithms and data structures class, I have to write an algorithm that is more efficient in the worst ...
