# Tagged Questions

2answers
146 views

2answers
67 views

### $O(n^{\log(n)})$ time algorithms

Is $O(n^{\log(n)})$ time algorithm considered of exponential time ? Is it applicable ?
1answer
34 views

### Generalization of Jacobi symbol for higher powers?

Let $n$ be an odd positive integer of unknown factorization, and let $x$ be relatively prime to $n$. The Jacobi symbol $\left(\frac{x}{n}\right)$ gives me partial information on whether $x$ is a ...
0answers
78 views

### Calculating time complexity of algorithms written in pseudocode.

Nowadays we are interested to find some algorithms with a prescribed running time. For example if for certain decisional problem $X$ there is an algorithm with running time $O(n^3)$ we try to break ...
1answer
80 views

### Mixed Q horn SAT

I am familiar with Horn formula: Formula whose clauses have atmost one positive literal. I am also familiar with Mixed Horn formula: Formula whose clauses are either 2 CNF or Horn. Question 1: But, ...
1answer
88 views

### Questions about a computer science field

I would like to have some information about the computer science field, " Algorithmic and Systems Analysis ". Is this a field of theoretical computer science? What subjects are related with this ...
1answer
47 views

### Prove that $\log n = O(\log^2 n)$

Trying to solve this, but I can't seem to figure it out. Its fairly straight forward.
1answer
29 views

### Why $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$?

I was told that the complexity of $T(n) = 2T(n-1) + O(1)$ is $\Omega(2^n)$; however, since I was not convinced, I searched in the Internet and all I found is that problem or very similar ones with ...
0answers
26 views

### Algorithmic Complexity of Linear Independence

Given n m-dimensional vectors. You can determine linear independence by Gaussian elimination. http://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency Checking linear independence ...
0answers
39 views

### Prove that (x+1)! is not O(x!)

Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ...
1answer
45 views

### Relation of encryption to P, NP, and NP-Complete

After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ...
2answers
58 views

3answers
62 views

1answer
48 views

### Union Find Program Prove By Induction

Consider the program below for building a union-find data structure. Prove by induction that if the method build_union is called starting with each vertex in a component by itself, that the ...
0answers
88 views

### A question on the computational complexity of Boruvka's algorithm

One algorithm that finds a minimum spanning tree in a graph in which all weights are distinct is Boruvka's Algorithm (also known as Sollin's Algorithm). On the page you would see once you clicked ...