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)

0
votes
0answers
18 views

Compare Complexity of Graph (Landau)

Assume I know that there is an algorithm of complexity $ \mathcal{O}( \vert V \vert^2 \vert E \vert ) $ for a Graph $G(E,V)$. How do I compare this for example to the complexity of $ \mathcal{O}( ...
1
vote
0answers
16 views

Does there exist a $k$ such that for all $n \ge 3$, $\text{gpf}(\lfloor n^{(\log{n})^k} \rfloor) \gt n$?

Does there exist a $k \in \mathbb{R}$ such that for all $n \in \mathbb{N}, n \ge 3$, $\text{gpf}(\lfloor n^{(\log{n})^k} \rfloor) \gt n$, where $\text{gpf}(x)$ is the greatest prime factor of $x$? I ...
0
votes
2answers
17 views

Bubble sort complexity calculation, unsure how it went from one step to another.

I'm looking at my textbooks steps for calculating the complexity of bubble sort...and it jumps a step where I don't know what exactly they did. I see everything up to that point using summation ...
2
votes
1answer
59 views

Math Contests: How to Solve Equation with $x$ in the Denominator

Okay, I realize this seems like a really stupid question, but on a math contest (without calculators) I got down to this equation: $$\frac{26}{672-x} + \frac{24}{372-x} = \frac{50}{480-x}$$ ...
0
votes
1answer
14 views

Prove that: $n^2+3n^3 + 6^{lgn} is $ $\theta(n^3)$

I'm asked to prove that: $n^2+3n^3 + 6^{lgn} is $ $\theta(n^3)$ I know that for Big O, I need to show: $f(n) <= c*g(n)$ But I'm not sure how to show this, since it involves theta. Any help would ...
1
vote
0answers
24 views

How long does the General Number Field Sieve actually take?

According to the researchers who cracked it, RSA-768 took an equivalent 2000 years to factor on a 2.2GHz single-core computer. Using the complexity equation for the General Number Field Sieve with ...
1
vote
1answer
26 views

First-order logic: largest size among smallest finite models for formulas of a given length

Apologies for the somewhat cryptic title. For any first-order formula X, let ssm(X) be the size of the smallest finite model of X. By size I mean number of individuals. So, for example, ssm('Fa ...
2
votes
1answer
12 views

Savitch theorem and its assumption

famous Savitch theorem states: For any function $f\in\Omega(\log(n)), \text{NSPACE}(f(n)) \subseteq > \text{DSPACE}((f(n))^2).$ Why we need an assumption that $f\in\Omega(\log(n))$? Thank ...
2
votes
0answers
31 views

Are binary bit-strings the most efficient representation of integers?

There is no format more popular in the world than the representation of Integers: 32-bit and 64-bit strings are used by basically every single computer in existence and there's no practical reason to ...
0
votes
0answers
16 views

What is an example of a search problem that is not in NP?

I feel like there should be an easy example, but I can't think of one. So, specifically, I am looking for a Yes/No search problem that is not in the class NP. When you learn about P and NP, you get a ...
1
vote
1answer
17 views

How to solve this recurrence $t(n) = ( 2^n )( t(n/2) )^2$ with $t(1)=1$?

I have been wondering about how to solve this recurrence but I don't get to any feasible solution. How can I do it?
0
votes
1answer
20 views

Find a function $f(n)$ such that neither $f(n) = O(log n)$ nor $f(n) = \Omega(n)$ holds.

Any hints on this problem? I want to find a function $f(n)$ which is: NOT $f(n) = O(log n)$ NOT $f(n) = \Omega(n)$ So it must hold that: $c_1 * log n < f(n) < c_2 * n$ and $c_1, c_2$ are ...
0
votes
2answers
62 views

An inequality on an arbitrary function

I'm trying to find the complexity of a program and reduced the question to the following one: Let $g$ be a function from natural numbers (including $0$) to natural numbers. Assume that for every $n ...
1
vote
1answer
23 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
29 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
23 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
37 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
22 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
14 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
10 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
24 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
51 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
31 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
24 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
52 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
11 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
28 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
31 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, ...
2
votes
3answers
82 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
23 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
32 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
29 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
15 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)$ ...
0
votes
0answers
29 views

Time complexity of $T(n) = 2^n + 2\sum_{i=1}^{n-2} T(i)$

$$ T(n) = 2^n + 2\sum_{i=1}^{n-2} T(i)$$ $$ T(0) = 1 , T(1) = 2 $$ This is my $T(n)$, and I need to find its time complexity. I know the answer is $T(n) = \theta (n2^n)$, but I have a problem with ...
1
vote
1answer
34 views

Runtime-complexity of a pseudo code.

Give an analysis of the running time of the following code snippet. ...
1
vote
1answer
30 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
26 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
43 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
0answers
25 views

Calculating run times of loops with theta notation using summation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. ...
-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
30 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
112 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
18 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
20 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 ...
-1
votes
0answers
16 views

A Standard Clique Reduction

We are working on complexity in my discrete mathematics class, and I'm trying to prove that the decision problem $3SAT(F)$ reduces to $CLIQUE(G,k).$ I have a feeling that what I need to do is, for ...