the amount of time resources (number of atomic operations or machine steps) required to solve a problem or run an algorithm with respect to the input size.
1
vote
0answers
26 views
Computational complexity of an algorithm
First I apologize if the title is unclear, but I didn't find anything better.
I want to find the boundary of (a simply connected) region in the $x-y$ plane. I'm solving a differential equation with ...
0
votes
2answers
38 views
Does reachability belong to P?
Reachability is defined as follows:
a digraph $G = (V, E)$ and two vertices $v,w \in V$. Is there a directed path from $v$ to $w$ in $G$?
Is it possible to write a polynomial time algorithm for it?
...
2
votes
1answer
34 views
Complexity of $Ax\geq 0$
May be it's a stupid question (sorry if it's the case).
What is the complexity the decision problem:
Input: $A\in\mathcal{M}_{n,m}(\mathbb{Z})$
does there exists $x\in\mathbb{N}^n,x>0$ such that ...
4
votes
0answers
41 views
Overlap Maximization problem
Here's the problem:
I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
2
votes
1answer
49 views
Lower-bound complexities for finding common elements between two unsorted arrays
I'm facing some problems that deal with finding common elements between unsorted arrays and I'd like to know whether there are well-known lower-bounds for the worst-case and, eventually, what are ...
3
votes
2answers
89 views
Modeling the problem of finding all stable sets of an argumentation framework as SAT
As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form.
Problem: Find all stable sets ...
2
votes
1answer
35 views
Confusion related to time complexity of dynamic programming algorithm for knapsack problem
I have this confusion related to the time complexity of the algorithm solving the knapsack problem using dynamic programming
I didn't get how the time complexity of the algorithm came out to be ...
-3
votes
0answers
39 views
Finding a better algorithm for a problem [closed]
Interval scheduling.
Job j starts at sj and finishes at fj
What is the best way to solve this?
2
votes
1answer
57 views
Time complexity in Big O notation for Harmonic series with first k terms missing
Firstly, let's suppose there exists an algorithm where $i$ iterates from $1$ to $n$, spending $\frac{n^2}{i}$ time in each iteration.
Thanks to the well known $O(\log n)$ upper bound for the Harmonic ...
2
votes
3answers
223 views
A Problem on Time Complexity of Algorithms
For every integer $t$, is there a problem whose solutions can be verified in $O(n^{s})$ time but cannot be found in $O(n^{st})$ time?
By verifying, I mean that given a candidate solution $y$, we can ...
1
vote
2answers
75 views
Why don't we scale the cost of memory access when analyzing runtime of algorithms?
Runtime for many programming languages is typically analyzed either assuming each operation takes a constant amount of time, or assuming each operation takes a logarithmic amount of time in the size ...
2
votes
0answers
25 views
Complexity of finding a subset of vertices within distance k of each other, given a set of vertices
I am trying to understand an algorithm presented in Using Stable Communities for Maximizing Modularity by S. Srinivasan and S. Bhowmick, along with its complexity results. (The complete algorithm is ...
0
votes
2answers
62 views
Algorithm analysis question in growth of functions
How would I solve the following.
An algorithm that is $O(n^2)$ takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500?
Can anyone help me ...
2
votes
2answers
33 views
Is the problem of evaluating a boolean formula on a given assignment P-complete?
I know that the CVAL problem is P-complete.
In the CVAL problem the input is a Boolean circuit together with an input to this circuit, and the answer is the evaluation of the given circuit on the ...
0
votes
3answers
140 views
Can all permutations of a set or string be generated in O(n log n) time?
I was looking over this question requesting an algorithm to generate all permutations of a given string. A comment in the answer caught my eye:
It might seem that it can take O(n) time per ...
0
votes
0answers
39 views
Finding average distance while travelling on an infinite wall
Ok here is the question:
There is an infinite wall with a hole somewhere, you are placed on that wall at a random position. Let the distance between your initial position & hole be X. Find the ...
5
votes
1answer
73 views
Time Complexity of a selection problem
I wonder what's the time complexity of the following selection problem I found while thinking of a string-matching problem.
[Assuming operations on integers take $O(1)$ time]
We are Given $m$ sets, ...
6
votes
0answers
60 views
FFT-less $O(n\log n)$ algorithm for pairwise sums
Suppose we are given $n$ distinct integers $a_1, a_2, \dots, a_n$, such that $0 \le a_i \le kn$ for some constant $k \gt 0$, and for all $i$.
We are interested in finding the counts of all the ...
0
votes
1answer
91 views
Does converting algorithms into elementary recursive form preserve runtime bounds? [closed]
There is the complexity class ELEMENTARY that captures all problems that can be solved by using elementary recursive function only. So if algorithms for solving problems in some complexity class (e.g. ...
6
votes
2answers
109 views
Can one show NP-hardness by Turing reductions?
In the paper Complexity of the Frobenius Problem by RamÃrez-AlfonsÃn, a problem was proved to be NP-complete using Turing reductions.
Is that possible? How exactly? I thought this was only possible by ...
3
votes
2answers
78 views
How is a witness found in a proof of $\mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$?
I'm having a hard time understanding the actual proof of this proposition:
$\qquad \mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$
The sketch of the proof is on slides 6-8 ...
2
votes
2answers
57 views
Why does a polynomial-time language have a polynomial-sized circuit?
I wish to understand why P is a subset of PSCPACE, that is why a polynomial-time langauge does have a polynomial-sized circuit. I read many proofs like this one here on page 2-3, but all the proofs ...
1
vote
2answers
93 views
How do we determine how much time a multi-tape DTM saves over a one-tape DTM?
Note: This is a part of a homework question
Were asked to construct a multi-tape Turing Machine for language {$a^n b^n c^n \mid n \geq 0$}
Then it says "Discuss how much time your machines saves ...
2
votes
1answer
41 views
Decreasing runs of inner loop in outer loop [duplicate]
I am trying to determine the worst case runtime of this program:
while n > 1
for i = 1,..,n
m = log(n)
n = n/2
Obviously the outer loop runs ...
1
vote
2answers
174 views
Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time?
The worst case running time of insertion sort is $\Theta(n^2)$, we don’t write it as $O(n^2)$.
$O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of ...
4
votes
2answers
59 views
Asymptotic Properties of Functions in Complexity Analysis
When dealing with the analysis of time and space complexity of algorithms, is it safe to assume that any function which has tight bounds ( i.e. $f(n)=\Theta(g(n))$ is asymptotically positive and ...
7
votes
4answers
80 views
Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded?
Does the difficulty of a strongly NP-hard or NP-complete problem (as e.g. defined here) change when its input is unary instead of binary encoded?
What difference does it make if the input of a ...
2
votes
2answers
72 views
How to Prove E $\subsetneq$ EXP?
I want to prove that $E \subsetneq EXP$ and i would like to do so using the Time Hierarchy Theorem
I need to choose $f(n)$, i think $2^{cn}$ is a good choice, so here is my Proof:
$E\subseteq ...
5
votes
2answers
222 views
Implement queue with a linked list; why would it be bad to insert at the head and remove at the tail?
In my textbook, Data Structures and Algorithms in Java, the author says when implementing a queue using a linked list you choose the front of the queue to be at the head of the list, and the rear of ...
2
votes
1answer
53 views
Not sure if my solution to following recurrence is correct
I have a recurrence relation, it is like the following:
$T(e^n) = 2(T(e^{n-1})) + e^n$, where $e$ is the base of the natural logarithm.
To solve this and find a $\Theta$ bound, I tried the ...
0
votes
0answers
17 views
The use of master theorem appriopriately [duplicate]
I have a recurrence relation and trying to use master theorem to solve it. The recurrene relation is:
T(n) = 3T(n/5) + n0.5
Can i use the master theorem in that relation? If so, can i say that ...
1
vote
2answers
69 views
Common Algorithms without Asymptotically Tight Bounds
I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds, but are there actually common algorithms in computer science that don't have asymptotically tight bounds ...
2
votes
0answers
78 views
Hash table collision probability
For an open-addressing hash table, what is the average time complexity to find an item with a given key:
if the hash table uses linear probing for collision resolution?
if the hash table uses double ...
3
votes
1answer
161 views
Time Complexity of Rabin-Karp matching algorithm
I asked a question on Rabin-Karp Searching algorithm here, which I am reading from the book "Introduction to Algorithms" 3rd edition Cormen et al..
After reading few para of the section on ...
2
votes
1answer
78 views
How to show that the complement of a language in $\mathsf P$ is also in $\mathsf P$? [duplicate]
If $L$ is a binary language (that is, $L \subseteq \Sigma = \{0,1\}^∗$) and $\overline{L}$ is the complement of $L$:
How can I show that if $L \in \mathsf P$, then $\overline{L} \in \mathsf P$ as ...
10
votes
6answers
375 views
What are the characteristics of an $O(n \log n)$ time complexity algorithm?
Sometimes it's easy to identify the time complexity of an algorithm my examining it carefully. Algorithms with two nested loops of $N$ are obviously $N^2$. Algorithms that explore all the possible ...
1
vote
2answers
99 views
What is the complexity of this matrix transposition?
I'm working on some exercises regarding graph theory and complexity.
Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically ...
-1
votes
1answer
58 views
Book to learn Algorithm Complexity
I need a good book which starts from quite beginner to learn about calculating the complexity of Algorithm??
9
votes
0answers
170 views
Complexity of deciding whether there is a winning strategy in the following game
The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 ...
2
votes
2answers
113 views
Finding the number of iterations to a recurrence
I have an algorithm where the number of items in my set decrease by $\sigma/(1+\sigma)$ on each iteration until all items are exhausted.
$$
\begin{align*}
S_0 &= S \\
S_{k+1} &= S_k - S_k ...
1
vote
1answer
30 views
Time complexity for modular arithmatic
I read about the time complexity for modular arithmetic in many books. There is one thing that I don't understand. I read in some books the following:
For any $a \mod N$, $a$ has a multiplicative ...
4
votes
6answers
347 views
Can every algorithm's running time be expressed as $\Theta(f(n))$?
That is, can the running time of every algorithm $A$ be written as $O(f_A(n))$ and $\Omega(f_A(n))$, for the same function $f_A$?
2
votes
2answers
139 views
Running time of a nested loop with $\sum i \log i$ term
So I have the following pseudo-code:
Function(n):
for (i = 4 to n^2):
for (j = 5 to floor(3ilog(i))):
// Some math that executes in constant time
So ...
0
votes
1answer
72 views
Big O time complexity
I have a question if I have my $k=300$
and my loop is like this :
for( int x = 0 ; x<n ; x--){
for(int y=0 ; y<k; y++){
...
}
}
Is this ...
3
votes
0answers
49 views
6-coloring of a tree in a distributed manner
I have some difficulties in understanding distributed algorithm for tree 6 - coloring in $O(\log^*n)$ time.
The full description can be found in following paper: Parallel Symmetry-Breaking in Sparse ...
7
votes
2answers
232 views
Why is push_back in C++ vectors constant amortized?
I am learning C++ and noticed that the running time for the push_back function for vectors is constant "amortized." The documentation further notes that "If a reallocation happens, the reallocation is ...
2
votes
1answer
79 views
Slow MIS Distributed Algorithm
I am interested in precise time complexity of distributed algorithm for finding MIS (Maximum Independent Set) of a given graph $G$.
I investigate the Slow MIS distributed algorithm (from these ...
0
votes
1answer
51 views
Time complexity of generating the first n primes and their product
Suppose that I have a turing machine that receives as input the string $1^{n\times n}$ (unary input), what is the time complexity of writing $p_1,...,p_n$ on the output tape, where $p_i$ is the i-th ...
9
votes
2answers
147 views
A dense NP complete language implies P=NP
We say that the language $J \subseteq \Sigma^{*}$ is dense if there exists a polynomial $p$ such that $$ |J^c \cap \Sigma^n| \leq p(n)$$ for all $n \in \mathbb{N}.$ In other words, for any given ...
2
votes
1answer
31 views
Computational complexity of coefficients
I have some recurrence relationships I use to compute some coefficients of a series. I want to know what the time complexity of computing these is. Suppose I know the coefficients $a_0,...,a_n$, and I ...
