Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computational-complexity]

Use for questions about the efficiency of a specific algorithm (the amount of resources, such as running time or memory, that it requires) or for questions about the efficiency of any algorithm solving a given problem.

0
votes
2answers
38 views

How to prove that $n^{n-2} = O(2^{n^2})$ [on hold]

I'm struggling to show that : $n^{n-2} = O(2^{n^2})$ . I know the definition of big O but I don't know any method to show this. Could you please help me giving a few methods?
0
votes
0answers
19 views

Fast inversion over large finite fields

I was wondering if there is a "fastest" way to compute inversions over finite fields, especially if they are very large. I know that the standard way is the extended Euclidean algorithm, which runs in ...
0
votes
0answers
10 views

time complexity for language

Assume that the language L has time complexity o(log n) on a deterministic decider Turing model. Can we deduce that L is a context-free language? Can we deduce that L is a regular language?
0
votes
1answer
27 views

Calculating Running time from Time Complexity

I have read about big $O$ notation for time complexity and for counting functions like that for prime numbers. Recently on StackOverflow I read: The problem with defining how long an algorithm ...
0
votes
0answers
22 views

Intuitive $O(n\, \text{log}(n))$ example

I'm having a hard time getting the intuition of an algorithm with worst-case complexity $O(n\,\text{log}(n))$. Is any informative example available?
3
votes
1answer
58 views

Big-$O$ of $ \log \binom{n}{n/2} $

I'm asked to evaluate this: $ \mathcal{O} \bigg( \log_2 \binom{n}{n/2} \bigg) $. I played with this a bit and I keep getting $\mathcal{O} (n\log n)$. When I substitute $n! = \sqrt{2\pi n} \Big(\dfrac{...
1
vote
0answers
3 views

Can the Borda count be used to select a distribution and not just a single choice?

Suppose I have n individuals and n unique, indivisible objects of potential value. I want to allocate those objects so as to make total welfare as great as possible, subject to the constraint that no ...
0
votes
2answers
37 views

Binary Addition Algorithm

I have to find the bit complexity, essentially the number of bit operations involved, in an algorithm to convert a number to its binary form. Here is the algorithm for a number n. X = binary ...
0
votes
1answer
16 views

Computational complexity of finding determinants

What is the computational complexity of finding the determinant of a matrix in this form? \begin{bmatrix} x_{1,1} & x_{1,2} & x_{1,3} & \dots & x_{1,n-1} & x_{1,n} \\ x_{...
1
vote
0answers
32 views

Generating random (torsion) point on elliptic curve efficiently

I am looking for an efficient way to generate a random point on an elliptic curve over a finite field, $E(\mathbb{K})$. I know that you can pick a random $x$, compute e.g. in Weierstrass coordinates ...
0
votes
0answers
34 views

Don't understand how log rules are applied in formula

On page 148 of Computational Complexity by Papadimitriou, it states: $nc_1^{f(n)} = c_1^{\log(n) + f(n)}$ I understand that I can expand the right part of the formula to $c_1^{\log(n) + f(n)} = c_1^...
0
votes
1answer
48 views

Is this proof Ok? ( about computing languages with no loops)

I know that a computing language that has no loops ( and therefore has only programs that stop on any input) doesn't have an interpreter. What's wrong with the following argument: If there's an ...
0
votes
0answers
14 views

Finding a dot product using queries.

Alice has two unit vectors, $x, y \in \mathbb{R}^n$. Bob wants to know the value $x\cdot y$. He is allowed to choose any vector $v \in \mathbb{R}^n$, send $v$ to Alice and she will send him $v \cdot x$...
0
votes
0answers
13 views

A few questions on the finite difference approximation for the heat equation

I'm trying to learn for fun how to apply the heat equation to different scenarios. Suppose I have a 2-D hotplate (perhaps steel) and on top of it sits a cube of some other material, and I'm only ...
0
votes
0answers
19 views

How can I prove that binary multiplication decision problem is solved in O(logn) space?

I can prove this if I use a NTM Turing Machine, but it is required to use a two-taped DTM, while taking into account only the space of the second "work tape"
3
votes
1answer
88 views

Algorithm for finding the smallest integer that satisfies several modular congruence conditions?

my first question! I work a lot with numbers (finance) but very much an amateur mathematician - please be gentle. I have the following problem that has come from discussions about cryptography: Given ...
0
votes
0answers
5 views

time complexity of a function to find minimum number of lines to cover all zeros in assignment problem

I am working on assignment problem by Hungarian method in O(n^3) polynomial time. To draw minimum number of lines to cover all zeros, i have got this function which is working really good. But can ...
1
vote
1answer
28 views

Decision function uncountable, why?

Good morning guys, I'm a new user of StackExchange, and I have already found here: Set of decision functions are uncountable However, I do not really understand the answer. I'm a student of Computer ...
1
vote
4answers
42 views

How many repetitions does the loop

Here is the following algorithm: for(k=2; k<n; k=k^k) I understand that I need to check when $n=k^k$. But I'm stuck on $k=log_k(n)$ How many repetitions ...
1
vote
2answers
39 views

Actual computational complexity of solving a linear system accounting for numerical accuracy (digit)

Solving a system of linear equations is solving for $n \times 1$ vector $x$ out of $Ax = b$, where $A$ is $n \times n$ matrix. Suppose that $A$'s entries have $k$ digits at maximum, in binary or ...
-1
votes
0answers
21 views

Can we calculate the complexity of this algorithm?

Can we calculate the complexity of this algorithm ? If yes,can anyone teach me how to calculate it? take this algorithm for example. i know the complexity we calculate is actually calculate the how ...
0
votes
0answers
16 views

Program complexity

We have a two-dimensional $n \times n$ array containing binary values binary ($0$ and $1$) where $0$ denotes a black pixel and $1$ a white pixel. Enter the number of square areas (with the same ...
0
votes
0answers
34 views

Complexity of the Newton's method approximation of $\frac{R}{b}$

I am trying to understand a particular concept in this lecture. The lecture goes on to describe that to compute a division of $\frac{a}{b}$, you have to: Compute high-precision representation of $\...
0
votes
0answers
87 views

Odds of drawing each card from partially known subset of cards

Say you have $6$ decks of $52$ suitless cards (so $24$ indistinguishable copies of each rank). From that, you're given a randomly chosen, shuffled subset $S$ of size $52$, of which half of the cards ...
0
votes
1answer
18 views

Find a number in unsorted array larger than the median number with complexity better than O(1/2n+1)

Given an unsorted array with N positive integers. Find a number in the array, that is larger than the median number in the array. for example if the array contains ...
0
votes
0answers
26 views

Using recursion tree to find time complexity of $T(n)=T(n/7)+T(3n/4)+cn$, where $c$ is a constant

After drawing the recursion tree,the longest path can be found,which is $1\to 3n/4\to\cdots\to(3n/4)^k$. So the length is $\log_{4/3} n+1$. Thus $T(n)\le cn[1+25/28+...+(25/28)^{\log_{4/3} n+1}]$. ...
0
votes
1answer
12 views

Clarification on the computational complexity of $f = x + \frac{c - \left| a^* x \right|}{\left| a^* x \right|} a \left( a^* x \right)$?

I am sorry for asking probably simple question regarding the computational complexity measure of the following function (I don't have a good background on these complexity measures). \begin{align} f = ...
0
votes
1answer
27 views

Doubt regarding the variable by which time complexity is measured

In order to assert that a given algorithm for graphs runs in polynomial time, must the variable in the big-O function that represents the run time (denoted henceforth as $O(f(n))$) be the number of ...
2
votes
2answers
50 views

Is there an algorithm to find the lengths of all paths from a given vertice that can run in polynomial time?

I have seen from a few sources (such as the CS Stack Exchange) that the problem of determining all the paths between two vertices $u$ and $v$ is NP hard. However, foR something that I am developing, I ...
1
vote
1answer
54 views

Efficient way to count the number of ways to select 3 numbers from a given list has their AND(bit-wise) equal 0

Suppose a list A contains non-negative numbers no larger than $2^8$. Eg. A = {4, 9, 6, 1, 15, 8, 3, 5, 18, 7} I want to find the number of selecting 3 members of A such that their AND bit-wise ...
1
vote
0answers
19 views

Computational complexity sum of digits square root

I know that the sum of digits formula is: $\frac{k(k+1)}{2}$ I am calculating the computation complexity of an algorithm whose while loop is increasing at this factor, hence: $\frac{k(k+1)}{2}>n$...
1
vote
1answer
28 views

Maximum cover with k element

I want to solve the following problem : For two set $\mathcal N$ and $\mathcal E$, we have a binary matrix $A$ index by $\mathcal N \times \mathcal E$ and we say that $e\in \mathcal E$ covers $n \in ...
4
votes
2answers
58 views

Minimum transactions to settle debts among friends

You are given $n$ integers $x_1,x_2,\dots,x_n$ satisfying $\sum_{i=1}^n x_i=0$. A legal move is to choose an integer $a$ and two indices $i,j$, and to increase $x_i$ by $a$ and decrease $x_j$ by $a$. ...
1
vote
2answers
342 views

Is it possible to know if a number exists within one of these sequences?

Question: Given a number, I need to find out which of the following rows/lists it exists in. But I don't want generate them, given that there are a lot of lists and they grow bigger over time. We ...
1
vote
1answer
28 views

Concluding about $f$ as a function $\mathbb{N}\to \mathbb{N}$ and finding complexity of a program

Problem unsigned int f(unsigned int n){ if(n==0 || n==1) return 0; if(n%2==0) return 1+f(n/2); return 1+f(5*n+1); } ...
0
votes
0answers
27 views

Time Complexity in finding the determinant of upper triangular matrix of order $n*n$

I am trying to prove that the time Complexity in finding the determinant of upper triangular matrix of order $n*n$ is $O (n)$ My Approach: Let us proceed this problem by taking an upper triangular ...
0
votes
0answers
12 views

Computational complexity and distinctions within categories.

In computational complexity, we can draw distinctions between space complexity and time complexity. But can we further draw distinction within space complexity? (e.g., and this is just an idea, but ...
-1
votes
2answers
48 views

Prove that $O(3^{2n}) \subseteq O(2^{3n})$

I need to prove that $O(3^{2n}) \subseteq O(2^{3n})$. So far I have made this solution: I)Lets assume that this is true, and that there $ \exists \space c \in \mathbb{R}^+ $ such as $$3^{2n} \leq 2^{...
0
votes
0answers
31 views

Runtime of computing the coefficient of a product of multinomials?

Suppose I have $k$ variables, $ x_1, x_2, ... x_k $ and $m$ expressions in the form $ (1 +$ the product of some subset of $x_1 ... x_k)$ – for instance, $(1 + x_1)$ or $(1 + x_1x_2x_5)$ could be one ...
0
votes
1answer
43 views

faster than O(n^4) algorithm for solving the following problem

This question is quite similar to the previous one I asked here. I recommend taking a look at it and the solution given by @platty before continuing. Given a set of n inequalities each of the form ax+...
0
votes
1answer
31 views

How to show divergence of $\sum_{n = 1}^{\infty} 2^{-o(1)}\frac{1}{n}$?

I am trying to show the divergence of the following sum: $$\sum_{n = 1}^{\infty} 2^{-o(1)}\frac{1}{n}$$ where the exponent of the 2 is negative little-o of 1. I have tried some ideas such as the ...
0
votes
1answer
42 views

faster than O(n^3) algorithm for solving the following problem

Consider the following problem: Given a set of n inequalities each of the form ax+by≤c for some a,b,c in Q, determine if there exists x and y in Q that satisfy all the inequalities. Here is an O(n3) ...
0
votes
0answers
14 views

How would I reduce the Minimum Vertex Cover problem to a Weighted MAX SAT problem?

I am currently trying to solve the Minimum Vertex Cover problem via a Weighted MAX SAT solver, but I am stuck with the model. The transformation to a simple SAT is straightforward since every node can ...
0
votes
2answers
49 views

Why Is This Algorithm Not In Polynomial Time?

so recently my professor went over this algorithm and stated that this is not a polynomial time algorithm due to n not being the length of the input. Can somebody explain why this is so? I didn't ...
1
vote
0answers
21 views

What is the fastest, free Weighted SAT solver?

I want to solve the minimum vertex cover problem by solving and equivalent SAT instance. I tried several solvers, but I didn't find any solver which does weighted SAT. Do you know of any free SAT ...
2
votes
1answer
50 views

Big O of multiple variables

Let $g(x, y, z)$ be a polynomial in the three variables $x, y, z$ that take values in $\mathbb{N}$. Prove that $g(x, y, z) = \mathcal{O}(x^k y^l z^m)$ for some $k, l, m \in \mathbb{N}$ I am not ...
1
vote
1answer
26 views

Because PvNP has yet to be proved does that mean that encryption might not exist? [closed]

I'm not well versed enough on the topic of computational-complexity theory but what I think I know is that there is debate over whether or not all problems that can be checked fast can be solved fast. ...
0
votes
0answers
22 views

Does Raz and Tal 2018 (linked) falsify the Extended Church-Turing Hypothesis?

In the paper Oracle Separation of BQP and PH, Raz and Tal exhibit an algorithm that is in complexity class BQP but not in PH. Question: Does their proof invalidate the Extended Church-Turing ...
0
votes
1answer
20 views

Complexity of Symbolic Matrix Multiplication

I am not sure if this is the right community in which to ask this question, but I'm trying to understand symbolic matrix math better, and cannot find many resources about it online. Specifically, ...
0
votes
0answers
18 views

Generalizing $n \cdot m = O(n^2) \iff m = O(n)$ to any two-variable function

I came across the following statement in my Computer Science high-school textbook (I translated it to English). There was some for loop that runs $m$ times nested inside a for loop that runs $n$ ...