complexity-theory 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
1
Since C++11, the C++ Standard Library (c.f. Section 25.4.1.1 of a draft verion of the standard) requires the std::sort algorithm to have asymptotic worst case execution time O(n log n) instead of a...
Slacks asked 17/3, 2021 at 8:47
10
Solved
I think this might be a classic question but I am not aware of an answer. Can a program output a copy of itself, and, if so, is there a short program that does this?
I do not accept the "emp...
Nanon asked 25/9, 2009 at 20:45
13
Solved
What are the differences between NP, NP-Complete and NP-Hard?
I am aware of many resources all over the web. I'd like to read your explanations, and the reason is they might be different from what...
Straightforward asked 7/12, 2009 at 1:11
1
You've written a yacc grammar (or some other LALR grammar in the tool of your choice), and you've decided that you want to refactor some productions for efficiency, clarity, whatever. For example, ...
Labanna asked 21/12, 2016 at 19:25
6
In .NET, is there a method, such as an event, for detecting when a console application is exiting? I need to clean up some threads and COM objects.
I am running a message loop, without a form, from...
Bonanno asked 13/7, 2009 at 14:38
5
Interview Question:
Edited Below
You are given an array. You make 2 heaps out of it, one minheap and the other max heap. Now find the median of the array using these 2 provided heaps in O(nlog n) ...
Kara asked 2/2, 2011 at 17:20
6
Solved
I know that Knapsack is NP-complete while it can be solved by DP. They say that the DP solution is pseudo-polynomial, since it is exponential in the "length of input" (i.e. the numbers of bits requ...
Magyar asked 27/12, 2010 at 12:19
6
Solved
I am trying to implement a plane sweep algorithm and for this I need to know the time complexity of java.util.HashMap class' keySet() method. I suspect that it is O(n log n). Am I correct?
Point o...
Monda asked 5/12, 2009 at 1:44
9
Solved
I have two input arrays X and Y. I want to return that element of array X which occurs with highest frequency in array Y.
The naive way of doing this requires that for each element x of array X, I...
Kish asked 23/3, 2013 at 21:9
9
Solved
I have got an array containing unique elements. I need to find out the first n largest elements in the array in the least complexity possible. The solution that I could think of so far has a comple...
Bess asked 1/9, 2011 at 15:22
3
Solved
This earlier question addresses some of the factors that might cause an algorithm to have O(log n) complexity.
What would cause an algorithm to have time complexity O(log log n)?
Papaw asked 9/5, 2013 at 22:13
7
Solved
This is my first course in data structures and every lecture / TA lecture , we talk about O(log(n)) . This is probably a dumb question but I'd appreciate if someone can explain to me exactly what d...
Dispirited asked 29/4, 2012 at 3:57
4
Solved
I had this exercice in an exam which stated:
Find an algorithm which can search for the highest number in an
unsorted list and have a Big-Oh complexity of O(log(N)).
The only searching algori...
Oculomotor asked 29/8, 2014 at 10:21
5
Solved
I am wondering if in a situation like the following (an if/else statement under a for loop) the complexity would be O(n) or O(n^2):
for character in string:
if character==something:
do something...
Tildy asked 1/7, 2015 at 14:51
2
Solved
I am a bit confused on space complexity. Is this O(1) space complexity or O(N) complexity?
Since I am creating a string of size n, my guess is the space complexity is O(N) is that correct?
## thi...
Dewitt asked 7/6, 2014 at 19:31
19
Solved
Can someone help explain how can building a heap be O(n) complexity?
Inserting an item into a heap is O(log n), and the insert is repeated n/2 times (the remainder are leaves, and can't violate the...
Etty asked 18/3, 2012 at 3:15
7
Solved
Say you want to iterate over a sequence [0 to n] in a random order, visiting every element exactly once. Is there any way to do this in O(1) memory, i.e. without creating an [1..n] sequence with st...
Donoho asked 17/9, 2012 at 13:41
7
Solved
I have a Computer Science Midterm tomorrow and I need help determining the complexity of these recursive functions. I know how to solve simple cases, but I am still trying to learn how to solve the...
Mandate asked 20/11, 2012 at 6:28
9
Solved
I know what is the difference between unshift() and push() methods in JavaScript, but I'm wondering what is the difference in time complexity?
I suppose for push() method is O(1) because you're ju...
Mofette asked 3/9, 2012 at 15:33
4
Solved
I'm trying to improve the speed of an algorithm and, after looking at which operations are being called, I'm having difficulty pinning down exactly what's slowing things up. I'm wondering if Python...
Unscathed asked 21/1, 2012 at 22:48
5
Solved
I'm pretty new to this stuff and I need your help.
I should build an efficient simple algorithm which returns the maximum value in an array with size of n which contains the numbers 1,2,...n with ...
Bilbo asked 31/10, 2012 at 13:53
3
I came across this passage on page 47 of Introduction to Algorithms by Cormen et al.:
The number of anonymous functions in an expression is understood to be equal to the number of times the asym...
Switcheroo asked 1/10, 2012 at 0:23
7
Solved
Is anybody able to give a 'plain english' intuitive, yet formal, explanation of what makes QuickSort n log n? From my understanding it has to make a pass over n items, and it does this log n times....
Liddell asked 3/5, 2012 at 5:16
8
Solved
We are used to saying that HashMap get/put operations are O(1). However it depends on the hash implementation. The default object hash is actually the internal address in the JVM heap. Are we sure ...
Elate asked 29/12, 2010 at 11:22
1 Next >
© 2022 - 2024 — McMap. All rights reserved.