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
83 views

the algorithm and computation cost for truncated SVD in rank k

It seems that the time cost of truncated SVD in rank k for matrix $A\in R^{m\times m}$ is $O(m^2 k)$. Could anyone show me some algorithms to calculate truncated SVD with the above time complexity?
1
vote
1answer
44 views

Formal definition of a set of graphs according to diameter restriction

I'm trying to find a formal way of defining the set of all directed graphs which their diameter is at most X, by formal definition I mean something of the following form: {G | G=(V,E) , G is a ...
1
vote
2answers
59 views

How to calculate the inverse of sum of a Kronecker product and a diagonal matrix

I want to calculate the inverse of a matrix of the form $S = (A\otimes B+C)$, where $A$ and $B$ are symetric and invertible, $C$ is a diagonal matrix with positive elements. Basically if the ...
0
votes
1answer
23 views

Computational complexity of Gauß-Seidel method

I'm currently studying iterative methods to solve equations of the form $Ax=b$ One method that is presented in my script is the Gauß-Seidel method where one step is defined as: $$x^{(k+1)} = ...
2
votes
1answer
81 views

Why are there no continued fraction representation for $\pi$ obeying mathematical rules?

There are several irrational numbers that can be represented with continued fraction such that a mathematical rule arises in this continued fraction. For example, the Euler number $e$ can be ...
2
votes
1answer
66 views

How to solve this logarithmic inequality?

I've started a data structure course and I need some help with solving these logarithmic inequalities. It would also be helpful because later on these kind of calculation won't pose a problem later ...
0
votes
2answers
43 views

Finding the biggest decrease in a list of integers (Python)

Given an array of n integers, h0, . . . , hn−1, I want to find the largest decrease in values such that the largest decrease is max(hi − hj) such that i ≤ j. For example, given as an input the array ...
0
votes
1answer
89 views

Computation complexity with simple algebra expression reduction

I'm watching this computer science video on computational time complexity of a function where they introduce some maths and it doesn't make sense to me. I'm not even sure what the name for this maths ...
1
vote
0answers
27 views

why some people use the notation $a \leq O(n)$?

When describing the algorithm complexity denoted by $c$, some people use $c \leq O(n)$ instead of $c =O(n)$ to show complexity. I cannot understand why they should use $\leq $?
0
votes
0answers
135 views

How to prove worst case time complexity for binary search

I have the following problem: Show that the worst case time complexity for Binary Search is given by: $W(n) = \lfloor lg(n) \rfloor + 1$ when n is not restricted to being a power of 2. ...
0
votes
0answers
26 views

How to find asymptotic cost of matrix filling algorithm . Big O Notation

So I have a list X of N strings each of length M that will be called x_i for the ith index in X Example ...
0
votes
1answer
45 views

How do we solve for $n$?

Asymptotic complexity gives an idea of how rapidly the space/time requirements grow as problem size increases. • Suppose we have a computing device that can execute 1000 complex operations per ...
0
votes
0answers
14 views

Lower bound for a difference

Let $x_1,\dots, x_n$ be $n$ positive real numbers. And $k$ be an integer with $k<n$ (in practice $n=k^2$ if it helps). I want to compute the smallest difference between the sum of two sets of $k$ ...
0
votes
0answers
34 views

Karatsuba's algorithm smart

I have a problem that I want to solve. I really tried but it does not budge. If the input is of size n for Karatsuba's algorithm We have three steps in Karatsuba's algorithm: 1) Recursively compute ...
0
votes
1answer
21 views

Big-O complexity of iterating over every substring

What is the Big-O complexity of iterating over every possible non-empty substring of a string of length $N$? The simple way to do the iteration over string $S$ is: ...
0
votes
1answer
14 views

Is CLIQUE PROBLEM polynomial on a class of graphs $\mathbb{G}$, if $\mathbb{G}$ has one graph.

By CLIQUE PROBLEM I mean whether $\omega(G) \geq k$ for $k \geq 3$. If $\mathbb{G}$ has just one graph, is the CLIQUE PROBLEM polynomial when restricted to $\mathbb{G}$? My Attempt: I can check ...
1
vote
1answer
33 views

Why do O(logn) & O(exp(n)) Have Polynomial & Non-Polynomial Running Time Complexities Respectively Despite Their Taylor Series?

I understand that a function, say $f(x)$, belongs to a class $O(g(x))$ iff: $$ \exists k > 0 \ \ \exists \ \forall n > n_0: |f(n)| \leq |g(n) \cdot k| $$ I also know that $log(x)$ is has ...
7
votes
2answers
252 views

Hamiltonian Weighted Graph and Decision Problems

I ran into a question on previous Mid-Exam. anyone could clarify me? Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight. Problem B: Given a Complete Weighted ...
1
vote
1answer
32 views

Theory of computation

For any language $A$, $B$ and $C$ such that $A\subseteq B \subseteq C$, if both $A$ and $C$ are decidable, then $B$ is decidable. True or False? How can I find this?
2
votes
1answer
33 views

Complexity class of conditional dependency resolution

I have a problem I am (considering) writing an algorithm for, but which I suspect to be NP-hard. However, I have not been able to prove that it is in fact NP-hard. The problem is stated as so: Given ...
3
votes
2answers
62 views

NP-Complete and Poly Time Reduction Problems [closed]

I Took Some Priminlairity Learning Method on Complexity Theory. I get trouble with some definition. anyone could help me, Why the mentioned statement is True? if a Problem A can be reducible to ...
0
votes
1answer
103 views

How to evaluate growth of input size from n to 2n in this case?

This is the question I am currently working on What is the effect in time required to solve a problem when you double the size of the input from n to 2n, assuming that the number of milliseconds the ...
3
votes
1answer
36 views

How to give an upper bound for a solution of $T(n) = T(0.25n) + T(0.75n) + O(n)$?

We have an algorithm which can be described the recurrence formula: $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n)$ and for $n\le 100$: $T(n) = O(1)$. How to show that $T(n) = O(n \log n)$? ...
0
votes
0answers
22 views

Shouldn't big oh definition be if and if only if, not just if? [duplicate]

This is from Discrete Mathematics and its Applications Shouldn't the if in that definition be an if and only if? Say we know that $n^2$ is in O($n^2$). Then from one side of the if and only if, we ...
0
votes
2answers
28 views

How to come up with an interval for this Big Oh Problem?

This is from Discrete Mathematics and its Applications I'am trying to use the interval method like what was shown in this example Here is my work so far: I noticed that when $x > 5$, $2^x > ...
1
vote
0answers
9 views

Factorization of sum and difference of factorized coprimes

If I have the prime factors of two coprimes $a$ and $b$, is it possible to find the prime factors of $a + b$ and $a - b$ faster than a full factorization?
0
votes
1answer
31 views

Construct a Turing Machine M' such that if M accepts a then M' accepts a and if M doesnot then M' does not halt

Give a TM $M$. Construct a Turing Machine $M'$ such that 1)if $M$ accepts $a$ then $M'$ accepts $a$ and 2)if $M$ does not accept then $M'$ does not halt. I am thinking about a 2-tape TM, with ...
30
votes
4answers
602 views

What is the *middle* digit of $3^{100000}$?

The decimal representation of $3^{100000}$ has $47713$ digits. What is the $23857^{th}$ digit - i.e. the one in the $10^{23856}$'s place? There are lots of questions on this site asking for the ...
3
votes
0answers
54 views

Category theory and complexity classes

Is there any interesting way to make the set of computational complexity classes into a category? Almost every interesting mathematical class of objects forms a category after all.
2
votes
1answer
50 views

Theory Of Computation - recognizable and decidable

How to prove that for any language $A$, if $A$ is recognizable and $A \leq_m A^\complement$, then $A$ is decidable. I know this theorem - A language is decidable iff both it and its complement are ...
0
votes
0answers
30 views

Computing a lower bound for the minimal componentwise distance of vertices of polyhedra

Let $A$ be a matrix in $\mathbb{R}^{m \times n}$ and let $P = \{ x \in \mathbb{R}^n \mid Ax \leq b \}$ be a polytope. I want to compute a lower bound on the minimal componentwise distance of two ...
0
votes
1answer
45 views

Decision Problems and Poly Time

We have Two Decision Problem A and B. we know A is NP-Complete, but B can be solved in $O(n^2lg^4n)$, and we know $B \leq_pA $ (i.e each problem of B can be convert to a problem of A in Polynomial ...
1
vote
1answer
55 views

Asymptotic and 3-SAT problem in Algorithm Course

my TA says just one of the following is True, anyone could describe me some detail about following three lines? 1- if $f_i$ be a function of natural numbers to natural numbers and $f_i(n)=O(n)$ then ...
0
votes
1answer
30 views

How may times should I colour a colour palette to have distinct colours?

Suppose that we have a colour palette, i.e., an array of n elements, which needs to be coloured by distinct numbers. We are only allowed to use 0 or 1 to colour every elements in each colouring step. ...
3
votes
1answer
55 views

Simple factorials

I've been doing some work with factorials and the normal way of calculating them is simply not working so well. When the numbers get really big, doing iterative multiplications is not viable and gets ...
0
votes
0answers
43 views

Best strategy for this archery-based probability game

This is with reference to the comments posted by @Trenin on my answer to this question. He says that since 2 players strategies depend on each other, we can't get the best strategy so easily. My ...
0
votes
1answer
42 views

How to give a big O estimate/visualize for these while loop?

This is from Discrete Mathematics and its applications I am currently working on problem 4. I was able to see that for problem 2, that one operation one will run n times for every n(meaning in ...
0
votes
1answer
24 views

Show the correctness: $\log^3( n)\in o(n^{0.5})$

show the correctness: $\log^3 (n)\in o(n^{0.5})$? I started from this way $$\log \log \log( n) = n^{0.5}$$ then I take $\log$ for two parties $$\log\log\log\log( n) = 0.5 \log( n)$$ ...
0
votes
0answers
41 views

How to show that $2^x$ is not in $O(x^2)$?

This is from Discrete Mathematics and its Applications I am working on 2e. I knew right off the bat from previous computer science courses that 2^x is not in O(x^2). I am having a difficult time ...
0
votes
0answers
29 views

Why can't this inequality hold true for all n > k?

This is from Discrete Mathematics and its Applications I am having trouble with why the "inequality n <= C cannot hold for all n with n >k". Is this reasoning for this that there is no largest ...
3
votes
3answers
50 views

Is there a clever shortcut to showing that this function is in O(N^2)?

This problem is from Discrete Mathematics and its Applications I am currently working on 2a. I am trying to apply an example the book gave earlier Is there some similar clever trick I can apply ...
0
votes
1answer
21 views

Fingerprinting and randomized algorithms

My question is regarding the notes pages 1-2 specifically http://www.cs.berkeley.edu/~sinclair/cs271/n3.pdf I understand everything up to the point near the top of the second page where it says ...
1
vote
1answer
18 views

Is there a typo in this runtime analysis of selection sort?

This is from https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-25/19-sorting2-select-insert-shell.pdf, slide 6. The instructor is doing a runtime analysis of selection sort. Here is ...
0
votes
2answers
15 views

Finding $2m+1=2\alpha k+\alpha^2$ quickly

Given some positive integer $m$ I'm looking for all solutions $\alpha,k>0$ to $2m+1=2\alpha k+\alpha^2$ with $0<k^2<2m.$ Right now I'm finding these by looping over each of these possible $k$ ...
1
vote
3answers
26 views

Recurrence Relations Closed Form

So, the question is to derive the closed form solution to the recurrence relation $$T(n) = 3T(n-1) + 5,\hspace{5mm} T(0) = 0.$$ $\begin{align}T(n) &= 3T(n-1)+5 \\&= 3(3T(n-2)+5)+5 ...
0
votes
1answer
21 views

Using limits to prove a function is in the order of another function

I have to prove the following theorem: I am not asking for the whole problem, but am stuck on the first part (Proving that output of c implies g(n) is in the order of f(n)). I know the following: ...
0
votes
1answer
29 views

Big Omega problem : is $n^2\in\Omega (2n^2)$?

Is $n^2\in\Omega (2n^2)$? If we find the limit we can see $\frac{1}{2}>0$, which means it is true, but I haven't learned the limit method. I need to figure out using this definition $\exists ...
0
votes
1answer
26 views

Need help figuring out $O(log$ $n)$ algorithm

Let's consider a strictly decreasing function $f : \mathbb{N} \rightarrow \mathbb{Z}$. That is, $f$ takes as input any natural number $(i ∈ N)$ and returns an integer such that for any $i$, $f(i) > ...
0
votes
0answers
23 views

Let g and h be any functions from naturals to (0,infinity)

Let $g$ and $h$ be any functions $\mathbb{N} \to (0,\infty)$. Then $g(n) \in \Omega(h(n))$ implies there is some $N \in \mathbb{N}$ such that $g(n)\ge h(n)$ for all $n \ge N$. Picture of question : ...
0
votes
0answers
16 views

How to calculate recurrence $F(n) = F(n/u) + \Theta(n^k)$ where $u,k \in \mathbb{N}$

$\Theta$ is used as in Bachmann-Landau notation (often called as Big-O notation convention). How does one in general the recurrence relation of the following from: $$F(n) = F(n/u) + \Theta(n^k) ...