Computational complexity, a part of theoretical computer science.

learn more… | top users | synonyms (1)

0
votes
2answers
22 views

How to show if a language is infinite, then there is no upper bound on the length of words in L?

L is a language over a finite alphabet. How to show that if L is infinite, then there is no upper bound on the length of the words within L? Can someone help me prove this.
4
votes
2answers
51 views

Optimal Box-in-a-Box-in-a-Boxing

As inspired by this closely related problem, suppose I have $n$ cuboid boxes, all with arbitrary (possibly random) finite dimensions. For any two boxes, $B_1$ with dimensions $w_1,h_1,d_1$, and $B_2$ ...
0
votes
1answer
22 views

Find $\sum_{i=0}^{\log n} \frac{1}{2^i}$

I'm not really sure how to solve summations, so any help would be great. In particular, I had thought that $n^2\sum_{i=0}^{\log n} \frac{1}{2^i}=O(n^2\log n)$ but it's actually $O(n^2)$, and I'm ...
2
votes
0answers
41 views

Is there a plausible outline of how geometric complexity theory could prove $P \neq NP$?

I've heard people saying that geometric complexity theory could be the key to showing $P \neq NP$, but when I've actually read about it it seems like it's concerned with other, perhaps analogous ...
-1
votes
0answers
15 views

How do I evaluate a summation for its comlexity? [closed]

Here, question #1 the answer is O(n^3), how do you solve for that? Why isn't it O(n)?
6
votes
2answers
178 views
+50

Why is there apparently a consensus on the P = NP question?

So through my years of education I have heard a lot about the famous $\mathrm{P}=\mathrm{NP}$ problem. I have seen that a significant number of mathematicians believe that this result is false (and ...
1
vote
1answer
47 views

N vs NP. Existence or Constructive.

I was discussing P vs NP problem with somebody who works in computer science. I work in mathematics and know very little about computer science. My opponent told me, if you solve P vs NP problem, ...
0
votes
0answers
31 views

How to prove that $f(n)=O(g(n))$ without using the definition of big oh?

I have to indicate for $f(n)=\log n$ and $g(n)=\sqrt[k]{n}$ if $f(n)=O(g(n))$ and if $g(n)=O(f(n))$. For $f(n)=O(g(n))$: I found it hard to prove it using the definition of big oh so I decided to ...
1
vote
1answer
13 views

Find functions which change asymptotic properties if raised to 2

Kindly give an example of positive functions f(n) and g(n) such that f(n) = O(g(n)) but it does not hold that 2^f(n) = O(2^g(n)). A friend asked this question as this came in one of his ...
2
votes
1answer
70 views

How to prove Big-Oh Equation e.g. $O({2}^{2n}) = O(2^n)$

I visit a course about complexity theory but I have some troubles to prove a Big-Oh equation like this: $O(2^{2n}) = O(2^n)$ $O(g(n))$ is a set of functions that fulfill following definition: The ...
1
vote
1answer
27 views

Complexity of finding $\alpha(G) + \omega(G)$

The CLIQUE NUMBER problem is NP Complete (due to correspondence with $3$-SAT); so is the INDEPENDENCE NUMBER problem (since $\omega(\overline{G}) = \alpha(G)$, or from CHROMATIC NUMBER problem). Can ...
1
vote
1answer
21 views

Strictly convex sequence

A sequence of numbers $A=(a_1, a_2, \dots, a_n)$ is called strictly convex, if there is a $k$, with $1 \leq k \leq n$ so that for all $1 \leq i \leq k-1$ we have $a_i>a_{i+1}$ and for all $k \leq i ...
0
votes
1answer
12 views

Asymptotic $T(n)=T(\sqrt{n})+1$

I would like to find the complexity of $T(n)=T(\sqrt{n})+1$ I did : $$T(n)=T(\sqrt{n})+1$$ $$T(n)=T(n^{1/2})+1$$ $$T(n)=(T(n^{1/4})+1)+1=T(n^{1/4})+2$$ And after $k$ steps : ...
0
votes
1answer
13 views

Dominant term- Complexity of function

I want to find the complexity of the function $g(n)=10 \cdot \log (n^{30}+30)+2$. We will find that $ g(n)=\Theta(\log n)$, right? But what can I say about the dominant term at the beginning?
1
vote
0answers
47 views

Datermine the time complexity of an algorithm calculating the sum of Euler $\phi$ function.

Firstly, the Euler $\phi$ function in this problem is same as wiki:Euler's totient function. The algorithm's input is a single number $N$, and its outpus is $\sum_{i=1}^n \phi(i)$. For simplify, I'd ...
1
vote
2answers
33 views

Which is the best way to find the complexity?

I want to find the asymptotic complexity of the function: $$g(n)=n^6-9n^5 \log^2 n-16-5n^3$$ That's what I have tried: $$n^6-9n^5 \log^2 n-16-5n^3 \geq n^6-9n^5 \sqrt{n}-16n^5 \sqrt{n}-5 n^5 ...
2
votes
0answers
51 views

Computing a “cheap” upper bound on the norm of the solution to a linear system

Consider the linear system $A x = b$, where $A$ is an invertible, $n \times n$, real matrix. I would like to compute a "cheap" upper bound on the (p-)norm of the solution; i.e. $\|x\|_p$. One can, of ...
1
vote
2answers
30 views

How do I find the big oh of $\sqrt[k]{n}$?

I have a problem where $f(n)=\log n$ and $g(n)=\sqrt[k]{n}$ and I have to prove that $f(n)=O(g(n))$. I'm using the big oh formula: $$ \begin{align} f(n)&\leq cg(n)\\ \log n&\leq c ?? ...
0
votes
0answers
25 views

Proving non-regularity of a language

How can I prove $L = (01^n2^n | n\geq 0)$ is not regular? Would it be sufficient to say that $01^p2^p$ is in $L$ and by pumping lemma, $01^p2^p$ can be written as $xyz$ such that $|y|>0, ...
6
votes
3answers
412 views

Is O(n) a proper class or a set?

Is $O(n)$ as the collection of all functions that are bounded above by $n$ a proper class or just a set? What about $O(\infty)$?
0
votes
2answers
24 views

Clarification on the big oh of the sum of two functions

In computing the asymptotic complexity of the sum of two functions, one theorem states that if $\large\lim_{n\rightarrow\infty}\frac{f_2(n)}{f_1(n)}$ exists, then the asymptotic complexity is ...
1
vote
0answers
50 views

Big-O estimate (smallest order)

I'm trying to give a big-O estimate for each of these functions, where I want to use a simple function $g$ of smallest order. I have them all done I just wanted to someone to run through and check ...
0
votes
0answers
16 views

Big Oh proof. Need help finding c constant

Ok I have the equation . I have compared each term with 2^n and proved that 2^n is greater for some n_0. My problem is how do I gather the terms up and find the c? $ \sqrt[]{2}^{\log n} + \log^2 n + ...
3
votes
0answers
111 views

indices set and halting problem in computation course

I ran into a multiple choice question that confused me with this notation. anyone could help me? this is adapted from an old class quiz in Calgary. Suppose A is be indices (i think index set) of type ...
6
votes
0answers
80 views

Challenge on Some Definition on Formal Language & Recursive & Automata

We know set A is countable if A is finite or in a one-to-one mapping to natural numbers. Suppose $\Sigma$ be an arbitrary finite alphabet. I summarize my inference: a) Each arbitrary Language on ...
3
votes
2answers
34 views

Is drawing the Voronoi diagram NP-hard?

Suppose we have a set of points in the plane. Is computational complexity defined to draw the Voronoi diagrams of these points? Since the plan is continuous I don't see how complexity can be defined. ...
0
votes
2answers
24 views

Word Form of Big O Notation

O of (the contents of the parentheses) Is this the correct way to say an expression with big O notation in words, just as y=f(x) is read y equals f of x? The expression with the big O followed by ...
1
vote
2answers
32 views

Is there a relationship between the clique of a graph and colouring of a graph?

Can one say that the minimum number of colours required to colour a graph (such that across any edge the two vertices have distinct colours) is lower bounded by the size of the maximum clique in the ...
0
votes
0answers
28 views

Help with understand the growth order of functions

I am taking an Algorithms class and I understand everything that relates to the asymptotic growth and Order of growth for a given function (Theta, Omega, etc). However, I am having trouble in ...
0
votes
0answers
13 views

Gauss Jordan vs Gaussian Elimination and Back Substitution Efficiency

I have an assignment that claims that Gauss-Jordan Elimination has the same efficiency Gaussian Elimination with back substitution. I get this part; but the assignment asks me to show that from a ...
1
vote
1answer
28 views

Multiply two polynomial in O(nlog n) time

In order to multiply two polynomial , we need O(n^2) complexity. Is it possible to perform the multiplication in O(nlog n) time??
0
votes
0answers
23 views

Hardest case in checking for hamiltonicity?

The problem of checking if a given graph has a hamilton-cycle, is NP-complete. However, in practice, the known algorithm work well. I wonder if sparse graphs (only a few edges) are more difficult ...
10
votes
2answers
271 views

Is there any infinite set of primes for which membership can be decided quickly?

The AKS algorithm decides whether or not $n$ is prime in time $\tilde{O}((\log{n})^6)$. I am wondering if there is any faster algorithm to determine membership in some infinite set of primes. What I ...
0
votes
0answers
32 views

Prove or Disprove Asymptotic Complexity

Not sure how to prove or disprove this. $$\min\{f(n), g(n)\} \in \Theta\left(\frac{f(n)g(n)}{f(n)+g(n)}\right)$$ Could someone please give me a hint on how to approach this?
1
vote
1answer
25 views

Recurrence Algorithms

What is the best method of solving non standard recurrence algorithms? In particular something like the following: What would be it's tight bound in Theta notation? $$ n \in N\\ T(n) = \sqrt{n} \; ...
1
vote
0answers
35 views

Constructing a “one-way function” of two variables (a.k.a “stop my friend from hacking my game”)

This might be more of a computer science question than a mathematics one; I thought I'd start here but perhaps people might want to point me to a better forum, if this isn't the right one. ...
0
votes
1answer
32 views

Proving $\lg n!=\Omega(n\lg n)$

In the answer given in the book for the proof of $\lg n=\Omega(n\lg n)$ there are several steps which I don't understand . $$\lg n!=\lg n+\lg(n-1)+\lg(n-2)+ ....+\lg(2)+\lg 1$$ Then it says that ...
0
votes
1answer
32 views

Does this loop run in $\mathcal{O}(n^4)$ time?

A double loop is given: int sum = 0; for (int i = 0; i < N*N; i++) for (int j = i; j < N; j++) sum++; My analysis: The inner loop runs $n$ ...
0
votes
2answers
40 views

Is my method of computing the running time correct?

Okay, so this is the code for which I need to compute the running time: ...
2
votes
1answer
33 views

Expected Value on code

I'm trying to figure out the expected number of times this algorithm will print. I'm stuck on how to go about doing so. I used an indicator variable to keep track of the number of print statements ...
0
votes
1answer
17 views

How to derive time complexity of following method.

I have one algorithm for which I have to find time complexity of number of time x=x+1 is executed: j=n; while(j>=1){ for i=1 to j x =x+1 j=j/2 } What ...
0
votes
1answer
55 views

What is the probability the best case occurs? (Comp Sci Type Question)

I'm having trouble figuring out what's the probability the best case occurs? It's my first time bringing together probabilistic knowledge into computer science. The question goes as such. Consider ...
0
votes
0answers
32 views

Find two element $x_k$ and $x_l$

Let $S=\{ x_1, x_2, \dots, x_n \}$ a set of real numbers, where $n \geq 2$. Describe an algorithm, that has time complexity $o(n^2)$ and that finds and returns two elements $x_k$ and $x_l$ of $S$, ...
1
vote
0answers
44 views

Efficient algorithm to find a minimum spanning set for a given vector.

A few days ago a colleague proposed the following problem. Let $W$ be a finite subset of a vector space $V$, and let $v\in\langle W\rangle$ (the linear span of $W$). Is there an efficient ...
0
votes
1answer
53 views

How to calculate running time of code?

I'm finding great difficulty calculating runtime with loops. It's easy when there is one loop, especially when the counter is being incremented by one: ...
0
votes
0answers
8 views

Lowest complexity matrix multiplication using parallelization

I'm not very familiar with complexity calculations (though I'm trying to learn), but what is the fastest published way to multiply two square matrices together with a GPU? The estimate I can come up ...
-1
votes
1answer
37 views

Prove or Disprove? $\log(n^n)\text{ is } \Theta(\log n)$

I need help confirming that my way of proof is alright. This is my first class in algorithms so I just wanna know if I'm on the right track. :)
1
vote
1answer
25 views

Big O complexity of the partition function derived from this code?

I am not able to calculate the Big O complexity of the partition function given in the code below. I tried to calculate it by estimating the number of nodes in the tree. So far, I've figured out that ...
1
vote
1answer
46 views

Finding pair of integers with given modulo

Given integer Goal and S = { X0, X1, ...., Xn } where Xi is a positive integer > 1, find a, b, in S and positive integer n (not necessarily in S) such that: a*n mod b = Goal E.g. Goal = 1, S = {3, ...
5
votes
2answers
76 views

Is $(\log(n))!$ a polynomially bounded function?

Is the following statement true? How would you prove it? i.e. Is it a polynomially bounded? $$ \lceil \lg(n) \rceil ! \in O(n^k) $$ How about $$ \lceil \lg \lg(n) \rceil ! \in O(n^k) $$ Thanks a ...