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
0answers
14 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
15 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
57 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
13 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
24 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
2answers
57 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 ...
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
16 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
19 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
1answer
24 views

Hardest boolean formula circuit complexity upper bound

I have stumbled upon Shannon's result that states that the maximum number of gates in a circuit needed to compute a boolean function on n bits, $f:\{0,1\}^n \to \{0,1\}$, is $\Theta (2^n/n)$. So far ...
1
vote
1answer
388 views

Pumping lemma proof of $L = \{a^nb^m \mid 0\leq n<m\}$

Prove the following language is not regular using the pummping lemma $L = \{a^nb^m \mid 0\leq n<m\}$ I tried solving this problem what I don't think I was able to reach an accurate proof. But this ...
1
vote
1answer
22 views

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

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
1answer
448 views

Big-O notation of $n^2/2+n/2$

I'm just starting to use big-O notation and I just wanted to make sure I was on the right track. My algorithm is the following: $$\frac12n^2+\frac12n$$ I came up with $O(n^2)$ is that correct?
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
40 views

What is the difference between “DTIME” and “Big O” notation?

I have some understanding of "big O" and "little O" notation. I have heard of "DTIME" but have not had formal education or training regarding its use. Can someone explain the difference (or ...
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}) = ...
3
votes
1answer
40 views

Abstract machines that compute primitive recursive functions

What it the simplest (least powerful) abstract machine that can compute primitive recursive sets, i.e. sets whose characteristic or indicator function is primitive recursive? ...
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 ...
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
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
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
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
35 views

How is $ BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $

I'm not able to understand how $BPP = BPP_{1/2+n^{-c}}= BPP_{1-2^{n^{-d}}} $ Can any body explain this to me in simple terms. Any help on this is highly appreciated.
-2
votes
0answers
15 views

Calculate full number of 7 card combinations beaten by my 7 card combo in texas poker. [closed]

Is there formula or algorithm for that? I can easily compare 2 seven card set but, is there formula for exact rank of my set? I am asking only about full 7 card sets.
-2
votes
0answers
16 views
0
votes
0answers
14 views

worst-case time complexity of bijective function [closed]

$A=\{a_1,a_2,\dots ,a_n\}; B=\{b_1,b_2,\dots,b_n\}$. Let $f:A\to B$ be a function.Write an algorithm in pseudocode that returns $1$ if $f$ is bijective and $0$ otherwise. And calculate the worst case ...
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 ...
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
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 ...
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
396 views

How do I prove an algorithm has $n^3$ time complexity?

Take the CYK algorithm outlined here: How to prove CYK algorithm has $O(n^3)$ running time In the top answer, how did that person go from the three summations to $t=(n^3−n)/6$ ? What's the method ...
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
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
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

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
0answers
60 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 ...
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: ...