time-complexity Questions
9
Solved
Among n persons,a "celebrity" is defined as someone
who is known by everyone but does not know anyone. The
problem is to identify the celebrity, if one exists, by asking the
question only of the fo...
Cimon asked 23/4, 2015 at 5:27
0
std::deque in C++ internally uses a segmented array, so how does it maintain O(1) time complexity when inserting at the front of the deque?
Segmented arrays break down the big array into smaller on...
Exarchate asked 28/6 at 7:33
7
Solved
I'm working on a HackerRank problem that's finding the largest sum of the elements in upper-left quadrant of a 2N x 2N matrix after reversing rows and columns. For example, if the matrix is
M = [
...
Microclimate asked 23/10, 2016 at 17:7
3
Solved
I have read that "the computational complexity of the Mersenne twister is O(p2) where p is the degree of the polynomial".
What does this mean?
Which polynomial is this referring to?
Also, is co...
Stingaree asked 3/9, 2014 at 18:46
3
Solved
I've been reading conflicting answers about modern javascript engines' time complexity when it comes to sets vs arrays in javascript.
I completed the demo task of codility, which is a simple assign...
Duren asked 10/12, 2020 at 17:53
1
I know about this question, but mine is a bit different.
Why does rehash have quadratic complexity, but operator [] (which can call rehash) has linear complexity in worst case?
Sorry, but I don't h...
Hep asked 9/2 at 18:40
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
2
Set has contains function which returns true if member exists in the set; otherwise, false.
and its complexity is O(1).
I want to know how its complexity is constant O(1) i.e. it does not depends...
Leong asked 8/5, 2018 at 18:56
12
Solved
What are some algorithms which we use daily that has O(1), O(n log n) and O(log n) complexities?
Conker asked 20/10, 2009 at 5:33
4
Solved
I have the memoization fibonacci code and I am having trouble figuring out what the time complexity is of it:
function fibMemo(index, cache) {
cache = cache || [];
if (cache[index]) return cache...
Levulose asked 6/3, 2017 at 3:52
3
Solved
According to some online sources I referred the runtime complexity of Floyd's cycle detection algo is O(n).
Say,
p = slow pointer
q = fast pointer
m = the distance from start of linked list to fi...
Congreve asked 9/11, 2017 at 3:7
2
Solved
I sorted four similar lists. List d consistently takes much longer than the others, which all take about the same time:
a: 33.5 ms
b: 33.4 ms
c: 36.4 ms
d: 110.9 ms
Why is that?
Test script (Attem...
Greggrega asked 5/3 at 15:21
2
Solved
I am trying to analyze the time complexity of the default integer square root function in Python 3.8+ versions, math.isqrt()
I have tried to peruse the time complexity of this function as a functio...
Furlough asked 26/2 at 18:53
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
16
Solved
I heard somebody say that since binary search halves the input required to search hence it is log(n) algorithm. Since I am not from a mathematics background I am not able to relate to it. Can someb...
Aurelie asked 18/11, 2011 at 15:50
5
I was coding a Euler problem, and I ran into question that sparked my curiosity. I have two snippets of code. One is with lists the other uses dictionaries.
using lists:
n=100000
num=[]
suma=0
f...
Incantatory asked 12/8, 2016 at 23:39
12
Solved
I just came around this weird discovery, in normal maths, n*logn would be lesser than n, because log n is usually less than 1.
So why is O(nlog(n)) greater than O(n)? (ie why is nlogn considered to...
Lintwhite asked 8/6, 2019 at 12:34
9
Solved
My professor just taught us that any operation that halves the length of the input has an O(log(n)) complexity as a thumb rule. Why is it not O(sqrt(n)), aren't both of them equivalent?
Pomfrey asked 4/2, 2017 at 8:39
3
Solved
Given an array of arbitrary numbers, I am looking to quickly [with time and space complexity lower than O(n²) at minimum, n = length of array] find the longest subarray (a contiguous segment of ele...
Redheaded asked 21/1 at 21:1
5
Solved
I was talking with a student the other day about the common complexity classes of algorithms, like O(n), O(nk), O(n lg n), O(2n), O(n!), etc. I was trying to come up with an example of a problem fo...
Vaporization asked 6/3, 2011 at 10:29
27
Solved
The majority element is the element that occurs more than half of the size of the array.
How to find the majority element in an array in O(n)?
Example input:
{2,1,2,3,4,2,1,2,2}
Expected outpu...
Carthage asked 1/12, 2010 at 14:11
4
Solved
I have the function below which searches an array for duplicate entries and then returns a list of the duplicates. I'd like to speed this piece of my code up, can anyone suggest a more efficient wa...
Suburb asked 3/10, 2017 at 23:22
6
Solved
An array is called "switching" if the odd and even elements are equal.
Example:
[2,4,2,4] is a switching array because the members in even positions (indexes 0 and 2) and odd positions (indexes 1...
Favourable asked 12/10, 2019 at 18:8
4
Solved
I am trying to understand the X and Y Fast Trie data structures and it's not clear why that structures are not used in large database since their asymptotic complexity is less than Log(N).
In cases...
Werewolf asked 13/10, 2014 at 17:34
8
Solved
The time complexity to go over each adjacent edge of a vertex is, say, O(N), where N is number of adjacent edges. So, for V numbers of vertices the time complexity becomes O(V*N) = O(E), where E is...
Coble asked 24/10, 2014 at 13:43
1 Next >
© 2022 - 2024 — McMap. All rights reserved.