All Questions
Tagged with algorithmscomplexity
70 questions
1vote
0answers
133views
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
-3votes
3answers
178views
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
-4votes
1answer
112views
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
0votes
0answers
96views
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
4votes
1answer
1kviews
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
0votes
2answers
1kviews
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
0votes
1answer
191views
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
5votes
4answers
641views
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
3votes
1answer
209views
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
21votes
6answers
5kviews
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
2votes
2answers
244views
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
-4votes
1answer
420views
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 ...
2votes
1answer
117views
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 ...
1vote
1answer
482views
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
0votes
1answer
41views
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
