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 ...
- 48.8k
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") } }...
- 48.8k
-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 ...
- 1,199
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
41votes
2answers
18kviews
What is O(...) and how do I calculate it?
Help! I have a question where I need to analyze the Big-O of an algorithm or some code. I am unsure exactly what Big-O is or how it relates to Big-Theta or other means of analyzing an algorithm's ...
- 48.8k
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 ...
- 34.7k
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)...
- 48.8k
18votes
3answers
21kviews
What does it mean by expected running time and average running time of an algorithm?
Let's say we want to analyze running time of algorithms. Sometimes we say that we want to find the running time of an algorithm when the input size is n and for the worst possible case it is denote it ...
- 119
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. ...
CommunityBot
- 1
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 ...
- 48.8k
-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 ...
7votes
3answers
15kviews
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 ...
- 9,129
