6,874 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
Advice
1
vote
4
replies
196
views
Best resources to learn Data Structures, Algorithms, and Big-O from scratch (for Python)
I want to learn Data Structures, Algorithms, and Big-O notation from scratch, but there are too many resources online and it’s difficult to determine which ones are trustworthy or widely used by ...
Advice
0
votes
4
replies
162
views
Why is my O(nlogn) solution faster than the O(n) solution
here is my solution to the leetcode "longest consecutive sequence" problem:
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if len(nums) == 0:
...
-3
votes
1
answer
197
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)
...
2
votes
3
answers
120
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....
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
214
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 ...
0
votes
1
answer
105
views
Asymptotic analysis: Time cost of allocating space for a set of elements
What is the time cost (asymptotically) of the following method?:
void fillList(int i)
{
list = new int[i];
}
I have been told that it takes O(1) time because no initialization is done and the ...
0
votes
1
answer
73
views
Couldn't understand on how lookup in a hashmap is O(N) while iterating over the same [duplicate]
I was doing leet code and came across https://leetcode.com/problems/two-sum/description/, which I've tried solving with a seen counter using hashmap. Below is the code:
class Solution:
def twoSum(...
-1
votes
1
answer
42
views
Does the value of n matter when comparing asymptotic complexities?
Is the complexity defined by the big-O notation e.g., n! is always more complex than n^3, regardless of the value of n?
What if I know n = 3? Would I be able to say that in this case O(n!) is less ...
0
votes
1
answer
117
views
Time complexity of dynamic programming
I'm looking at one of the solutions to the programming problem: Partition a Set into Two Subsets of Equal Sum. The programming problem: Given an array arr[], the task is to check if it can be ...
0
votes
2
answers
104
views
Space complexity of the array passed function
I am confused by the space complexity of the function below:
int sumArr(int a[], int size) {
int sum = 0;
for (int i = 0; i < size; ++i) {
sum += a[i];
}
return sum;
}
In ...
2
votes
0
answers
37
views
What is the complexity of 2D array graph traversal? [duplicate]
Whether it is BFS or DFS, is it (MN)^(MN)? There're M*N nodes and, in the worst case, all the nodes have edges between each other.
0
votes
0
answers
73
views
How to Calculate Time Complexity Using Recurrence Tree for T(n) = T(n - sqrt(n)) + n^2
I'm trying to analyze the time complexity of the following recurrence relation using the recurrence tree method:
T(n) = T(n - sqrt(n)) + n^2
The challenge I'm facing is determining the height of the ...
5
votes
1
answer
122
views
Asymptotic behaviour of recursive algorithm
I'm having trouble understanding why the first function below is asymptotically 2^n, whereas the second is 3^n. I understand that solving the recursion equation yields these results, but am having ...