Computational complexity, a part of theoretical computer science that deals with understanding how efficiently a problem can be solved.

learn more… | top users | synonyms (1)

1
vote
1answer
25 views

How to show the running time of the following algorithm? [closed]

The outer loop runs n times. The inner loop runs Math.floor(n/i) times. So it would be O(n*Math.floor(n/i)). I do not know how to transform that into a proper expression involving Big Oh and n. Maybe ...
0
votes
0answers
9 views

What is the complexity of the arithmetic operations in base $b$?

Fix a number $n$. We want an algorithm which takes a positive integer $x$, represented as a base $b$ string, and outputs the base $b$ representation of $nx$. Note that if $n$ is a power of $b$, there ...
0
votes
1answer
31 views

There is no algorithm which has a runtime of $O(n^2)$ and $\Theta(n^\frac{7}{2})$

How can I proof that there exists no algorithm which has a runtime of $O(n^2)$ and $\theta(n^{\frac{7}{2}})$? Or is this possible because logically I would say that if a function is ...
0
votes
0answers
6 views

A special case of the boolean multivariate quadratic polynomial problem

It's well known that in the general case, the boolean MQ problem: given $(f_1, \ldots, f_n) \in \mathbb{F}_2[x_1, \ldots, x_m]$ with $\deg(f_i) = 2$, can we find a solution $\vec{y}: f_i(\vec{y}) = ...
1
vote
2answers
27 views

Time Complexity Calculation

I'm currently working a few exam question, and got stuck at this point. I am given that a Quicksort algorithm has a time complexity of $O(nlog(n))$. For a particular input size, the time to sort the ...
1
vote
0answers
45 views

How can I plot the complex function in 2D?

My function: $$sin(wt-jT) \tag{1}$$ where $j$ - complex unit, $T=0.1,\ w=8 \pi,\ t=[0,0.01,0.02..100]$ I transform it to function with real arguments: $$\sin(wt)\cosh(T)+j\cos(wt)\sinh(T) ...
0
votes
1answer
25 views

Help solve a computational complexity problem

Find the tight computational time ($\Theta$ notation) complexity of the following function Of course an exact solution is $\sum\limits_{i = 1}^{3{n^3}} {\frac{{2{n^3}}}{i}} $, but I am not able to ...
1
vote
0answers
18 views

Applying the convolution theorem in the presence of a twiddle factor

The convolution theorem says that a 2-d cyclic convolution like $C = U \ast V$ can be evaluated more quickly than doing the raw sum $C_{i,j} = \sum_{a,b}^n U_{a,b} V_{i-a,j-b}$ for each point (assume ...
1
vote
0answers
12 views

A polynomial majority function

Let us introduce a boolean function $F(x_1,x_2,x_3,...,x_n)$, where $F=1$ when most of the variables $x_1,x_2,...,x_n$ are equal to $1$ and $F=0$ otherwise. This is called a majority function. The ...
1
vote
1answer
34 views

Smart way to calculate floor(log(x))?

I thought of an algorithm that involves $\lfloor \log_{b} x \rfloor$ and am trying to determine its computational complexity. At first glance my algorithm looks polynomial, but I read that my ...
2
votes
1answer
56 views

If someone finds a polynomial time algorithm for a problem in NP, will we be able to construct polynomial time algorithms for all problems in NP?

The existence of a polynomial time algorithm for a single problem in NP implies the existence of polynomial time algorithms for all problems in NP (correct me if I'm misunderstanding this). Suppose ...
1
vote
0answers
32 views

How to resolve this computability paradox?

Let's define two Turing machines, $T_1$ and $T_2$, as follows: Given a number $n$ as input, let $T_1$ be a Turing machine that enumerates over all pairs $(p,s)$ where $p$ is the code of some Turing ...
0
votes
1answer
35 views

Can we solve this recurrence relation using recursion tree method

The recurrence relation is given as follows: $T(n) = 2T(\sqrt{n})+1$ $T(1) = 1$ I tried to solve it with recursion tree as follows: But to find the number of levels that may occur, I have to ...
0
votes
1answer
55 views

Why do people say that some problem is hard when they do not actually prove it?

I have read many times in different papers something like the following (I do not remember the exact words though): "The problem is nonlinear non-convex programming problem which is hard to ...
0
votes
0answers
14 views

How to show that if a relativized PH collapses, then PH collapses itself

Due to a lack of activity on the CS.SE, I'm asking this question here. Let $A$ be an arbitrary set in PH. Suppose PH$^A$ collapses. I am now asked to show that PH itself must collapse. I have ...
0
votes
0answers
30 views

The complexity of bubble sort and insertion sort for a list with a given number of inversions

Let the length of a list be $n$, and the number of inversions be $d$. Why does insertion sort run in $O(n+d)$ time and why does bubble sort not? When I consider this problem I am thinking of the ...
0
votes
0answers
55 views

Calculating the average case complexity for finding the maximum number in an array

Algorithm: Given a non empty array with $N$ Numerical values, the algorithm finds the location LOC and the maximum value MAX of the largest element of DATA. Initialize K:= 1, LOC:=1, ...
3
votes
3answers
89 views

Why isn't integer factorization in complexity P, when you can factorize n in O(√n) steps?

It is said that integer factorization is an NP problem. Why isn't it P? You can solve it in $O(\sqrt{n})$ time with trial factorization, and since $\sqrt{n} = n^{1/2}$, to me that looks like a number ...
0
votes
1answer
39 views

Factorial grow faster than Exponential - permutation case

It is said that factorial grows faster than exponential, but in the case of permutation: ...
0
votes
0answers
35 views

Converting a for loop to a sum

I'm trying to convert the following for loops to sums, but I'm getting a little confused about the upper limits: for(i=2; i <= n; i*=i) ...
0
votes
0answers
34 views

Complexity analysis of finding the roots of a polynomial

Hypothesis: all the set elements and polynomials (coefficients) are defined over a field $\mathbb{F}_p$ where $p$ is a large prime number. .................................................... ...
0
votes
1answer
16 views

What's the complexity class of Sub-Polytrees isomorphism?

In terms of Subgraph isomorphism I believe Directed Acyclic Graphs (DAG's) are in the np-complete complexity class. What about Poly-trees (oriented trees)? These are DAG's where the possible paths ...
0
votes
1answer
15 views

How do you express “additional complexity”?

Let's say I have two algorithms, one of which is less efficient in the sense that the complexity in the $\mathcal{O}$ notation has an additional factor $n$ (so for example, one is $\mathcal{O}(n^2)$ ...
1
vote
1answer
38 views

Runtime-complexity of a pseudo code.

Give an analysis of the running time of the following code snippet. ...
1
vote
1answer
35 views

Show that a Function is Big Theta Using Limits

I'm asked to show that: $f(n) =n^2+ 3n $ is $ \theta$$(n^2)$ using limits. I know that without limits I can usually solve for a constant, and easily show that this is true, but I'm not too familiar ...
2
votes
4answers
38 views

O(n) of given code

sum = 0 for (i = 0; i < n; i++) for (j = 0; j < i * i; j++) for(k = 0; k < n; k++) ++sum Here is my work The outer most loop: ...
1
vote
1answer
35 views

Meaning of “polynomially larger”

For example Is $n$ polynomially larger than $\frac{n}{\log n}$? Than $n \log n$? Is $n^2$ polynomially larger than $\frac{n}{\log n}$? Than $n \log n$? I am trying to understand the difference ...
0
votes
0answers
46 views

Simplify sum with binomials

An algorithm finds prefixes of given length k from given word with length n. It is required to find the time complexity of given algorithm. It is easy when no nodes get cut off in its recursion tree ...
-1
votes
1answer
37 views

Conditions for embedding between non-oriented graphs [closed]

I have the following assignment on my Algorithms Analysis course. Given two undirected graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ with $\operatorname{card} (V_1) < \operatorname{card} (V_2)$ ...
0
votes
1answer
36 views

How to find the Big-O of the difference/quotient of two funtions

I'm not sure if what I'm asking even makes sense but it's a property of big-O that if $T_1(n) = O(f(n))$ and $T_2(n) = O(g(n))$, then $T_1(n) + T_2(n) = O(f(n) + g(n))$, or less formally its ...
1
vote
0answers
27 views

What is the Computational Complexity of Minimising a Linear Function over a General Convex Set?

Is the computational complexity of finding or approximating $\inf\{c^Tx:x\in X\}$ (where $X$ is a compact convex given explicitly or by some reasonable oracle) known? EDIT: Suppose we had an ...
0
votes
0answers
118 views

Counterexample for Algorithm of Isomorphism testing of Non-Symmetric Matrices

Claim: $E, F$ are non-symmetric 0-1 matrices of dimension $m \times n$ where $m>n$. Given $F \neq E$, it takes maximum maximum $O( \frac {m^{log_2(m)}} { 2^{\sum log_2(m)} })$ times to check ...
0
votes
2answers
24 views

Design a finite automata by checking division of number of characters

I need to design and draw a finite automata that can accept the letters {a,b}. The number of the the letters a should be devided by 3, and the number of the letter b should be devided by 2. For ...
0
votes
1answer
22 views

complexity of building heap: why can one substitute a bounded infinite series into a bounded sum?

Partially into the derivation, the author substitutes the result of this infinite series, $$ \sum_{h=0}^\infty hx^h = \frac{x}{(1-x)^2} $$ into the bounded sum, $$\sum_{j=0}^h ...
0
votes
1answer
29 views

Big-O complexity of calculation: Drawing a non-colliding subset of k elements from n total

I'm trying to understand the computational complexity of this pseudocode: ...
0
votes
0answers
27 views

Arithmetic complexity of mod powers

Given $a,b,p\in\Bbb N$ what is the computational complexity of computing $a^{p^b}\bmod p$? Is it $O((\log a)(\log b)(\log p))$ arithmetic operations on $\log p$ sized words? $p$ need not be prime.
1
vote
0answers
26 views

“Relative unsatisfiability” of SAT instances

There's a natural way to view any SAT instance as a variety: just replace the Boolean algebra $2$ of truth values with the corresponding Boolean ring $\mathbb{Z}/2\mathbb{Z}$. (See my answer to Is ...
5
votes
2answers
175 views

Is there an equivalent concept of a “variety” for SAT?

Couldn't find anything via google - I was wondering what work is out there looking at SAT problems from the perspective akin to an algebraic variety, e.g. a set of variables $X_1=$true, $X_2=$false, ...
1
vote
1answer
46 views

Why can't this be done with Master Theorem

Apparently recurrences like this cannot be solved with the Master Theorem: $T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$ Because $n^{\log_b(a)} = n^1$ is not a polynomial multiple of $f(n) ...
0
votes
1answer
14 views

Estimate logarithmic complexity

I have data (running time $T$ and problem size $N$). If I suspect that there is a polynomial relationship in the form $T=a N^b$, I can plot a log-log graph and work out the gradient, as stated on the ...
-4
votes
1answer
33 views

Compute bits per second [closed]

We know a computer can code 1024 bits/sec using a RSA modulus of 1536 bits and the running time of modular exponential with modulus $n$ is $O(\ln^3(n))$. Using a key of 2048 bits, how many bits per ...
3
votes
1answer
65 views

Problems in NP but not in NPc

Are there currently any known problems that are in NP but are known not to be NP complete?
1
vote
0answers
61 views

A polytime language with no subsets of lesser time complexity

For any integer $l>0$ does there always exist a language with time complexity of order $O(n^l)$ such that it has no subsets of a lesser time complexity ie $O(n^m)$ for any $m< l$. We talk of ...
4
votes
1answer
249 views

Algorithm. Minimum area of a square enclosing given set of points .

I am learning about the science of algorithms and I'm studying some problems with their optimum algorithm. The problem I describe below is one of them. I need a lower and an upper bound of its ...
1
vote
2answers
48 views

$2^{O(\log \log n)} = O(\log n)$ prove or disprove

I need to prove or disprove this: $$2^{O(\log\log n)} = O(\log n)$$ I haven't found anything like that through search. I would like to have some help. Thanks.
1
vote
2answers
44 views

How can I solve this logic statement with explanation?

There is a pack of cards and every card has a number on one side and a letter on the other. The statement that every card in this pack that has an A on one side has a 3 on the other side is true. The ...
1
vote
0answers
14 views

How to adjust finite differencing method for mapping from $\mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ where $n = m^{2}$?

So I'm supposing $F:\mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ is differentiable, and I have MatLab code that evaluates $F$ at an arbitrary $x$ in $q$ flops. I know that given $F(\bar{x})$ where ...
1
vote
2answers
39 views

Computable problem

A mathematical problem is computable if there is an algorithm that decides/solves this problem, right? Can you give an example of such a problem?
6
votes
0answers
56 views

Find a region with maximum sum of top-K points

My problem is: we have $N$ points in a 2D space, each point has a positive weight. Given a query consisting of two real numbers $a,b$ and one integer $k$, find the position of a rectangle of size $a ...
7
votes
3answers
140 views

Computing the first $n$ values of the Liouville function in linear time

Is it possible to compute the first $n$ values of the Liouville function in linear time? Since we need to output $n$ values we clearly cannot do better than linear time, but the best I can figure out ...