# Tagged Questions

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

88 views

### “Balancing” two infinities

Given these two computational complexities of 2 algorithms: $\exp(O(\sqrt{\log n \log \log n}))$ $O(\sqrt{\exp n} / \log{ \sqrt{ \exp n} })$ where I imagine the first one goes to infinity slower ...
294 views

### Is there a function that only generates primes?

The title sums it up: does there exist a "nice" injective function $f(n)$ such that $f(n)\in\mathbb P$ for all $n\in\mathbb N$? I'm having difficulty specifying exactly what I want "nice" to mean, ...
147 views

### How to find $(-64\mathrm{i}) ^{1/3}$?

How to find $$(-64\mathrm{i})^{\frac{1}{3}}$$ This is a complex variables question. I need help by show step by step. Thanks a lot.
13k views

### What is the time complexity of Euclid's Algorithm (Upper bound,Lower Bound and Average)?

I looked it up online in many sites but none give a clear answer. They all give a lot of complicated mathematical stuff which is not only hard for me to grasp but also irrelevant as I simply want to ...
41 views

### Why does it take maximum of $n/\log n$ digits to represent the number $2^n - 1$ in base of $n$?

Given the number $n$. Why does it take maximum of $\frac{n}{\log n}$ digits to represent the number $2^n - 1$ in base of $n$?
1k views

75 views

135 views

### Möbius function help

Given some large random integer k, how much longer would it take to determine the primality of k, then to calculate mobius(k), and how much longer would it take to factor k, then to calculate mobius(k)...
67 views

266 views

### solving a non-standard recurrence relation in asymptotic terms (using Big O notation)

Looking at the following recurrence relation: $$T(n)= T(n-x)+T(x)+O(\min(x,n-x))$$ $$T(1)=1$$ where $x$ can devide our problem in any proportion (may vary from call to call -- not a constant ...
2k views

### If an unary language exists in NPC then P=NP

I've a question regarding a theorem in Complexity Theory. It is said that if there exists an unary language in NPC then P=NP e.g if {1}* in NPC then the above is correct. It means that there exists ...
345 views

### approximation of binomial coefficient sum

I would like to find some approximation or upper & lower bounds on the next simple expression: \begin{align} \sum_{i = 0}^{k} \binom{h}{i} \qquad h \geq k \end{align} But I need this ...
1k views

### Baker-Gill-Solovay theorem

I have been trying to understand the proof of Baker-Gill-Solovay theorem as described in Complexity Theory: Modern Approach. I think I do understand most of it, but what troubles me is that let's say ...
63 views

### What is this number $k$?

I'm reading A first Course on Logic, (Hedman). An algorithm is said to be polynomial-time if there is some number $k$ so that, given any input of size n, the algorithm reaches it's conclusion ...
51 views

### How would you write this sentence

I'm writing a short document about an integer programming (IP) problem instance. I've mentioned that IP is known to be NP-Hard, but that being NP-Hard doesn't automatically qualify this particular ...
143 views

### Prove that the little-o definition doesn't hold for two function (f and g)

I need your help with the following statement: Show there exist two function $f(n), g(n)$ such that meet the following definition: $g(n) = O(f(n))$ and $f(n) \ne O(g(n))$ But don't meet the little-...
161 views

### What would be complexity of computing $3^{n^n}$?

Just curious, what would be the computational complexity of computing $3^{n^n}$? I am not sure what it would be like.
240 views

### Some Big-O complexity definition proofs

I'm trying to prove (by definition) the following but to no avail: $n^{n/2} \ne O(3^{n/2})$ $n! \ne O(3^n)$ $(n-b)^a = \Theta(n^a)$ $a,b$ are both constants whereas $a > 0$ and $b$ ...
3k views

### Little-o proof by definition

I'm trying to figure out how to prove the following but to no avail. Given the following functions : $f(n) = n^3 -4n$ $g(n) = 5n^2 + 3n$ I have to show that $g(n) = o(f(n))$ by definition, that ...
192 views

### NP-complete Problems

It seems from reading that problems are determined to be NP-complete if they can be shown to be equivalent to another NP-complete problem. However, I wonder how the "original" NP-complete problem was ...
463 views

### Order of magnitudes comparasions

I have a list of order of magnitudes I want to compare. My only idea is using calculus methods (limits , integral, etc...) to assert the functions relation. I need your help with the following. I ...
88 views

### Big-O compared to a new Operator

I'm trying to figure out a new operator compared to the Big O. Suppose we have two positive functions, $f(n)$ and $g(n)$ then we say that $f(n) = O^*(g(n))$ if there exists a constant $c > 0$ ...
33 views

### Weird BigOmega statement - Totality

I've just encountered a weird statement regarding the BigOmega operator. I should prove that the BigOmega operator isn't totally ordered. As a prove hint, I should show that there are two functions, ...
414 views

### Difficulty proving / finding witnesses for the following Functions (Big O and Big Ω and $\Theta) I have left with some functions I can't find witenesses for proving Big O and Big Ω and Big$\Theta$relations. Notice that I should prove the following using the defintion and not any complex ... 1answer 2k views ### Orders of Growth between Polynomial and Exponential What is known in contemporary mathematics about orders of growth for functions that exceed any degree polynomial, but fall short of exponential? This is a subject for which I've found little ... 1answer 174 views ### Understanding of working of Turing Machine for$\{0^k1^k\}$I try to learn Computation Complexity by Sipser's textbook "Introduction to the Theory of Computation". The problem is I have a lack in understanding how Turing Machine is working. Example from the ... 0answers 47 views ### How can i count the number of flops of the following expression? lets say, after Cholesky factorization, at some point in my solution I get this:$L_{11}*L_{11}^T=A$,$L_{11}*L_{21}^T=u$,$L_{21}*L_{11}=u^T$, and$L_{21}*L_{21}^T=a$So,$a$is a scalar,$u$and$...
I have to prove the following statement: $$f(n) + g(n) \in \Omega(f(n))$$ I am not sure what to do. Can I use this somehow?  f(n) \in \Omega(g(n)) : \iff 0 \le lim_{n \rightarrow \infty} \frac{f(...