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,636
6
votes
5
answers
2k
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 ...
- 161
6
votes
2
answers
7k
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 accounting ...
- 299
5
votes
3
answers
6k
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 ...
- 61
5
votes
1
answer
10k
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 ...
- 261
5
votes
4
answers
684
views
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)...
- 187
5
votes
2
answers
1k
views
Algorithm to find Minimum bounding rectangle of fixed area [closed]
I have set of spatial points defined by coordinates (x,y) . I want to find the bounding rectangle of given area that maximizes the number of point inside the rectangle. The obtained rectangle should ...
- 59
5
votes
2
answers
397
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 ...
- 51
4
votes
2
answers
303
views
How can I know when a paper is too hard for me to be able to implement their code and/or understand their math - within a given deadline?
I've been assigned to explore implementing (along with modifications, so understanding it is a must) this algorithm for the 'Redistricting Problem': https://dl.acm.org/doi/pdf/10.1145/3274895.3274979 ....
- 49
4
votes
3
answers
319
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 ...
- 614
4
votes
1
answer
2k
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:
...
- 827
4
votes
1
answer
1k
views
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
4
votes
1
answer
219
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; h++)...
- 165
4
votes
1
answer
169
views
Are these graph coloring algorithms equivalent?
Suppose you want to color the vertices of a graph in a greedy fashion, given a predetermined order of these vertices. The goal is to avoid giving two adjacent (linked by an edge) vertices the same ...
- 151
3
votes
6
answers
888
views
Is it better to write an efficient algorithm or code that is easier to understand?
So I was recently given a coding assignment from a large financial firm, and I thought of two ways to solve the problem. One of the ways involved 1 outer for loop and 1 inner for loop. In this case, ...
- 89
3
votes
1
answer
436
views
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
3
votes
2
answers
31k
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 ...
- 225
3
votes
1
answer
320
views
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 ...
- 51
3
votes
3
answers
6k
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 ...
- 191
3
votes
2
answers
10k
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 ...
- 35
3
votes
4
answers
8k
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 ...
user145653
3
votes
2
answers
1k
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 j=i+...
- 139
3
votes
1
answer
665
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 ...
- 185
3
votes
1
answer
553
views
Algorithms comparison and complexity
I want to sole this problem:
Write a method to return all valid combinations of n-pairs of
parentheses.
The method should return an ArrayList of strings, in which each string
represents a ...
- 159
3
votes
3
answers
3k
views
Are there any programs or IDEs that calculate Big-O notation on functions? Is this something that is possible to program into an IDE?
Is there anything that can calculate the Big-O notation of a function?
While learning about Big-O, it is implied that it is pretty trivial to do in your head once you know the basic rules, however if ...
- 3,649
3
votes
0
answers
235
views
String Pattern Matching from Lookup Table - Non-Exponential Solution?
Given the problem...
Given a String comprising of non-alhpabetical symbols, and a Lookup
Table where a subset of those symbols may equate to a single
alphabetical character, output all possible ...
- 131
2
votes
7
answers
4k
views
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 ...
- 147
2
votes
4
answers
3k
views
What is Big-O notation for purely functional languages?
Is it still relevant?
Instead of
var result = new List<int>();
for (var i = 0; i < prev.Count; ++i)
{
result.Add(prev[i] * 2);
}
where the result.Add, prev[i], and * 2 instructions are ...
- 151
2
votes
7
answers
580
views
What is wrong with this algorithmic solution of mine that checks whether a given function returns a sorted array when an array is given as input?
An interviewer asked me this question:
Given a function f(ar[]) where ar[] is an array of integers, this
functions claims to sort ar[] and returns it's sorted version ars[].
Determine if this ...
2
votes
4
answers
1k
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 (...
user53019
2
votes
4
answers
16k
views
Finding the time complexity of the following program that uses recursion
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 &...
- 313
2
votes
1
answer
25k
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 ...
- 41
2
votes
3
answers
2k
views
Is the Time complexity of this function o(n) ? Can it be optimized any further?
This is a very simple function to find if a string is composed of unique characters. I believe that this is a O(n) time complexity as it loops once and has a single if condition. Am I correct? Is ...
- 133
2
votes
3
answers
443
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 ...
- 123
2
votes
1
answer
595
views
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 ...
- 39
2
votes
1
answer
1k
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; j++)
...
- 145