10,335 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
1
answer
92
views
Why does this iterative parentheses generation have fewer operations than the divide-and-conquer approach despite generating duplicates?
I'm solving LeetCode 22 - Generate Parentheses and came up with an iterative approach that builds combinations by inserting () at every ( position, plus prepending/appending. Despite my approach ...
-2
votes
0
answers
124
views
Is it faster to calculate integer exponentiation with binary or ternary chunks? [duplicate]
Code 1
In code one we are using the binary exponentiation.
public class Solution {
public int pow(int A, int B, int C) {
if (C == 1) return 0;
long base = (A % C + C) % C;
...
Advice
0
votes
7
replies
141
views
Is it reasonable to understand binary search through the intuition of a normal distribution?
While studying binary search, I intuitively connected it to the idea that a normal distribution concentrates probability mass near the center.
Binary search always examines the midpoint first, which ...
6
votes
2
answers
406
views
Efficient algorithm to count contiguous subarrays that can form arithmetic progressions
I'm working on a problem where I need to count, for each possible common difference D, the number of contiguous subarrays whose elements can be rearranged to form an arithmetic progression with common ...
-3
votes
1
answer
196
views
Monotonic Stack Algorithm: Is the Average Time Complexity θ(n) or O(n)? [closed]
The algorithm I've written for an assignment is closely related to this monotonic stack approach
https://www.geeksforgeeks.org/dsa/next-greater-element/
Best case:
n pushes → Time complexity: O(n)
...
Best practices
0
votes
3
replies
63
views
Compare fingerprints with a set of 10*10^6 other audio fingerprints in postgres
So I have a function that I used to compare audio fingerprints with a few thousand audio fingerprints stored in a postgresql. What I did basically was:
def my_function(cur: Cursor, threshold: ...
user avatar
user31692560
-5
votes
1
answer
87
views
Asymptotic time complexity where a variable has a known upper bound?
Say I have an algorithm that runs in O(N*M + N + M). Say that although M can vary, it can only be between 1-20. For asymptotic complexity is M treated as a constant? Because you can't really take the ...
2
votes
3
answers
119
views
Big-O notation if n is a constant [duplicate]
Let's say I have this pseudocode:
int n = 100
for (int i = 1; i<=n; i++)
System.out.println("Hello!");
for (int j = 1; j<=n; j++)
System.out.println("World!!!");
end
...
0
votes
1
answer
68
views
Dotnet LINQ expressions time complexity
Considering elements as a list of objects (already loaded in memory, not a DB query) and given the following portion of code:
var filteresElements = elements.Where(el => el.Flag == true).Select(el....
2
votes
1
answer
304
views
Minimum cost to convert all 1's to 0's using window of size k
There is a row of toys, where each toy is represented as either:
1 → red toy (needs to be painted blue),
0 → blue toy (already painted).
An integer k is given. An operation can be performed as ...
-1
votes
4
answers
175
views
How can I optimize the time complexity of my brute-force solution for finding all unique triplets with sum zero?
I'm solving the "3Sum" problem where I need to find all unique triplets in an array that sum to zero.
Here’s my brute-force Java code:
public List<List<Integer>> threeSum(int[] ...
4
votes
2
answers
280
views
What is the time complexity of the following algorithm:
int k = 0;
for (int a = n; a >= 1; a /= 2)
for (int b = a; b >= 1; b--)
k++;
cout << k;
I would say that the answer is O(n), but the book where I have found the exercise says that ...
1
vote
2
answers
213
views
Big O for possibly non terminating algorithm
Suppose we want to generate a 5-digit unique student ID
i.e. there are N = 100,000 possible values (from 00000 to 99999).
What is the big O of the algorithm below?
- while True:
- Generate a random ...
4
votes
2
answers
145
views
Is it feasible to compute all simple paths between two nodes in a large directed graph (26,000 nodes, 86,000 edges)?
I have a large directed graph (not a DAG) with about 26,000 nodes and 86,000 edges. I want to find all possible simple paths (no repeated nodes) from one given node to another.
How difficult or ...
-3
votes
2
answers
94
views
Time Complexity Of A Recursive Function
I have a function of following form that I would like to know the time complexity of:
recursiveFunction(List<Input> list, int leftIndex, int rightIndex){
if(rightIndex <= leftIndex){
...