All Questions
Tagged with algorithm-analysis complexity
14 questions
0
votes
2
answers
363
views
fastest way to find number of smaller elements to the right of an array
In Daily Coding Problem, Miller&Wu have the following problem :
Given an array of integers, return a new array where each element in the new array is number of smaller elements to the right of ...
- 181
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
0
votes
2
answers
1k
views
Calculating time complexity of a code snippet
I am trying to calculate the time complexity of the below code snippet
def func()
{
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j=j+i)
{
print("hello")
}
}...
- 111
5
votes
4
answers
641
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
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
2
votes
2
answers
244
views
Time complexity for a small code
I'm trying to find the time complexity for the following code.
N= number of elements in array
D= a constant: D>1
V= a constant: V>1000
counter=1; //the maximum value of the counter is N/D.
...
- 37
-1
votes
2
answers
312
views
Why in Tournament Sorting do we neglect the number of comparisons to find the Minimum?
Here the professor said that, Tournament sort needs (n-1) + 2(n-1)logn comparisons.
{Where (n-1) for calculating Maximum or say creating Tournament structure
and
2(n-1)logn for other elements to sort}...
- 47
-4
votes
1
answer
100
views
Calculating Complexity
I am having trouble calculating the complexity of this problem:
REVERSE3(A): // Reverse the order of elements in an array
// P is an array; assume generating next permutation takes 1 step.
for ...
- 103
3
votes
1
answer
549
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
2
votes
4
answers
3k
views
How does the dividing Step in Merge Sort have Constant Time Complexity?
I am highly confuse while calculating time complexity of Merge Sort Algorithm.
Specifically on the Dividing Step.
In the dividing step we have to calculate the mid point of "n" i.e. "q = n/2".
How ...
- 47
-1
votes
3
answers
507
views
Time complexity of an algorithm [closed]
What is the complexity of the following loop?
for(i=1;i<n;i=2^i)
sum+=i;
- 11
1
vote
3
answers
2k
views
What's the big-O complexity of this recursive algorithm?
I am following a course of Algorithms and Data Structures.
Today, my professor said the complexity of the following algorithm is 2^n.
I waited till the lesson was over, approached him and told him ...
- 119
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
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