space-complexity Questions
8
Solved
Let's take this implementation of Merge Sort as an example
void mergesort(Item a[], int l, int r) {
if (r <= l) return;
int m = (r+l)/2;
mergesort(a, l, m); ------------(1)
mergesort(a, m+1, r);...
Howes asked 26/4, 2012 at 23:37
1
Solved
I'm doing this basic dp (Dynamic Programming) problem on trees (https://cses.fi/problemset/task/1674/). Given the structure of a company (hierarchy is a tree), the task is to calculate for each emp...
Thibeault asked 15/2 at 17:30
2
Solved
f (int n){
if (n<=0){
return 1;
}
return f(n-1) + f(n-1);
}
Suppose we did f(4). My thought was that it would be O(2^n), since then in order to find f(n-1) + f(n-1) we would have to push f...
Sumbawa asked 8/11, 2015 at 2:51
7
Solved
There is an array related problem, the requirement is that time complexity is O(n) and space complexity is O(1).
If I use Arrays.sort(arr), and use a for loop to one pass loop, for example:
publi...
Jugum asked 21/3, 2014 at 23:57
3
=SUM(SEQUENCE(10000000))
The formula above is able to sum upto 10 million virtual array elements. We know that 10 million is the limit according to this question and answer. Now, if the same is im...
Mide asked 22/9, 2022 at 13:10
2
I've been doing some reading about hash tables, dictionaries, etc. All literature and videos that I have watched imply to hash-tables as having the space/time trade-off property.
I am struggling ...
Triglyph asked 19/3, 2014 at 10:10
5
This is the recursive implementation of the Fibonacci sequence from Cracking the Coding Interview (5th Edition)
int fibonacci(int i) {
if(i == 0) return 0;
if(i == 1) return 1;
return fibonacci(...
Vargueno asked 27/2, 2015 at 1:33
16
Solved
In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.
This question was asked by Stripe in it's programmi...
Habituate asked 15/7, 2018 at 7:13
2
Solved
I've heard of a class of data structures called succinct rank data structures. What do these data structures do? What does "succinct" mean here? And how do they work?
Savonarola asked 11/6, 2022 at 0:11
6
Solved
Given the function below:
int f(int n) {
if (n <= 1) {
return 1;
}
return f(n - 1) + f(n - 1);
}
I know that the Big O time complexity is O(2^N), because each call calls the function tw...
Gavrilla asked 8/4, 2017 at 18:37
4
Solved
This is slightly confusing to me. What should be my approach of solving a given problem when the constraint is as follows:
1) Without using extra space:
For e.g.: If I want to sort a given array,...
Nussbaum asked 1/6, 2012 at 4:3
3
Solved
This is the Daily Coding Problem:
“Given a singly linked list and an integer k, remove the kth last element from the list. k is guaranteed to be smaller than the length of the list.
The list is v...
Haematozoon asked 21/10, 2018 at 23:47
0
Can anybody please explain the calculation of time and space complexity of this code(finding determinant of a matrix) in detail?
I am not able to understand the exact time complexity of this progra...
Lotty asked 22/5, 2021 at 10:28
2
Solved
My main concern with recursion is the recursion limit in Python, which I think is 1000. Taking this into account, I want to discuss two scenarios:
Scenario 1: Applying recursion for a balanced tree...
Diathermic asked 28/3, 2021 at 13:46
6
Solved
Using Bloom filter, we will be getting space optimization. The cassandra framework also has an implementation of Bloom Filter. But in detail, how is this space optimization achieved?
Flagellate asked 28/12, 2010 at 13:35
5
Solved
I was working on a Codility problem:
You are given two non-empty zero-indexed arrays A and B consisting of
N integers. Arrays A and B represent N voracious fish in a river,
ordered downs...
Tamera asked 14/3, 2018 at 21:53
3
Solved
From what I understood in Wikipedia's explanation of quicksort's space complexity, quicksort's space complexity comes from its recursive nature. I'm curious as to whether it's possible to implement...
Ascendancy asked 12/7, 2012 at 15:27
0
I want to check the space complexity of
matrix inversion,
matrix adjoint and
matrix determinant.
Most of the literature mention the time complexity (for the inversion there are $O(n^3)$ soluti...
Monde asked 6/7, 2020 at 3:19
4
Solved
Suppose that n records have keys in the range from 1 to k.
Write an algorithm to sort the records in place in O(n+k) time.
You may use O(k) storage outside the input array.
Is your algorithm stab...
Arletha asked 28/3, 2013 at 12:41
7
Solved
Given n positive real numbers in an array, find whether there exists a triplet
among this set such that, the sum of the triplet is in the range (1,
2). Do it in linear time and constant space.
...
Mascon asked 24/10, 2013 at 5:15
9
Solved
You are given an array of integers. You have to output the largest range so that all numbers in the range are present in the array. The numbers might be present in any order. For example, suppose t...
Giorgi asked 24/3, 2011 at 5:53
1
Which is a faster method? like aren't they both the same?
start = time.time()
arr = np.array([1,2,3,4,5,6,7,8,9,0,12])
total_price = np.sum(arr[arr < 7])* 2.14
print(total_price)
print('Durat...
Larval asked 21/5, 2020 at 23:25
3
Solved
I am having a hard time understanding what is O(1) space complexity. I understand that it means that the space required by the algorithm does not grow with the input or the size of the data on whic...
Matney asked 6/4, 2017 at 16:31
1
I have a problem which requires a string to be transformed into another one by appending copies of its' initial value to itself. The problem allows to remove single characters at some places.
Expl...
Jollanta asked 3/12, 2018 at 19:35
4
Solved
I am writing a blogpost on Python list.clear() method where I also want to mention about the time and space complexity of the underlying algorithm. I expected the time complexity to be O(N), iterat...
Fijian asked 30/11, 2019 at 6:24
1 Next >
© 2022 - 2024 — McMap. All rights reserved.