All Questions
Tagged with complexity algorithms
70 questions
1
vote
0
answers
133
views
Ideal Profits in companies in Perfect Binary Search tree
I'm trying to solve the following problems here:
In the X world, companies have a hierarchical structure to form a large binary tree network (can be assumed to be a perfect binary tree). Thus every ...
- 111
-3
votes
3
answers
178
views
NP-complete problem (subset sum) featured in Netflix series "Suits" S1 E8? [closed]
In the Netflix series Suits, Season 1, Episode 8 (Identity Crisis), the legal team, with the help of a hacker, is tasked with proving that a business magnate embezzled funds, splitting them and ...
- 203
-4
votes
1
answer
112
views
What is the big O of this algorithm? [duplicate]
I think it's O(m*n) but someone said it's O(n). If you think it's O(n) could you provide an explanation?
def convert(self, s: str, numRows: int) -> str:
if numRows == 1:
return ...
- 103
0
votes
0
answers
96
views
O(nlogn) + O(logn) =? [duplicate]
So I came upon this time complexity result and I was confused about it, it said that :
O(nlogn) + O(logn) =O(log(n+1))
Why is that the case? Shouldn't the result be O(nlogn)?
- 27
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
0
votes
1
answer
191
views
How should I apply dynamic programming on the following problem
I have an array of events where events[i] = [startDay_i, endDay_i, value_i]. The ith event starts at startDay_i and ends at endDay_i, Attending the ith event, I will receive value_i. Also given an ...
- 23
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
3
votes
1
answer
209
views
Nested loop complexity
I am working through MIT 6.006 OpenCourseWare as taught in Fall 2011. Problem 1.2c asks for the time complexity of an algorithm1 which finds a peak element (i.e. all neighbors are less than or equal) ...
- 141
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
-4
votes
1
answer
420
views
What is the worst case Time Complexity for only the Divide Portion of the Merge Sort Algorithm?
Please, consider the below merge sort algorithm. Here we start with a divide portion which splits the array into halves and we do recursive operation on each half separately. I have ignored the merge ...
- 1
2
votes
1
answer
117
views
Quantity allocation algorithm performance
I have a scenario for which I'll take an analogous example to help understand better.
There are N buckets of known varying capacities.
We have M balls that we need to put in these buckets to fill ...
- 129
1
vote
1
answer
482
views
How to identify additional space complexity
I just started leaning about algorithm design and I am now having trouble identifying the additional space used in an algorithm. For dynamic program, as far as the examples I've learnt, such as ...
- 113
0
votes
1
answer
41
views
Assembling random indexed packages into an ordered sequence(s)?
I am pretty confident that this is well-known and solved problem.
Suppose there are n uniquely indexed "packages" randomly getting into single entry point like .AcceptPackage(Package package). ...
- 345