# Tagged Questions

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

69 views

40 views

### MATLAB “back slash” computation [closed]

I am looking at a MATLAB code that times the backslash operator for several cases. I will list the cases below: Note: all of these are for m = 5000 1) Z = randn(m,m); A = Z'*Z; b = randn(m,1); tic; ...
40 views

### How many arithematic operations(flops) are to $n×(n+1)$ matrix of system?

Source: Linear Algebra and Its Applications David C. Lay A system of n equations in n unknows correspond to $n×(n+1)$ augmented matrix. One book says the reduction(elimination) to echelon form can ...
17 views

### Hardness of approximation for linear equations

Given a system of linear equations in n variables with coeffcients that are rational numbers, determine the largest subset of equations that are simultaneously satisable. Show that there is a ...
43 views

### Fast algorithm to recognize sortable sequences

Every sequence is sortable in the worst-case by a $O(n^2)$. However, if we restrict sorting primitive, we get an interesting problem. I am interested in this sorting problem: Input: a sequence $A$ of ...
52 views

### Good books on Algorithms for a math major without any programming experience?

I couldn't find this question anywhere else so it may not be apt. I am an undergraduate mathematics major and during my discrete math class I really enjoyed the study of algorithms and recursive ...
41 views

36 views

### Prove that for every function $s:\mathbb N\to \mathbb N$ with the following constraints holds that:

Hello guys I'm studying Computational Complexity and I have stumbled upon the following question which I has no idea how to even start proving. I would appreciate any help. Prove that for every ...
36 views

### Why these algorithms have a linear complexity function?

Considering the following algorithms: ...
44 views

### What are the minimum hard constraints that cause the nurse scheduling problem to be NP-complete?

A client wishes to simplify the nurse scheduling problem to 'bypass' the NP-complete nature of this problem. He is hoping to do so by removing the requirement that there are any constraints for any ...
40 views

### When is $(mn+1)/(n-m)$ an integer?

For an integer $n$ I would like to find all integers $m$ with $n/2<m<n$ and $$\frac{mn+1}{n-m}$$ an integer, that is, $$mn\equiv-1\pmod{n-m}.$$ How can I find these $m$? I could just check ...
49 views

### Complexity of recurrence equation 6

$B(n)=B(⌈ n/\log_2 n⌉)+\theta(n)$ B(2)=1 Here is my attempt: \begin{align*} B(n) &= 3B(\lceil n/\log_2 n\rceil) + \Theta(n)\\ &= 3\big(3B(\lceil n/(\log_2 n)^2\rceil) + \Theta(n)\big) + \...
31 views