# Questions tagged [time-complexity]

The amount of time resources (number of atomic operations or machine steps) required to solve a problem expressed in terms of input size. If your question concerns algorithm analysis, use the [runtime-analysis] tag instead. If your question concerns whether or not a computation will *ever* finish, use the [computability] tag instead. Time-complexity is perhaps the most important sub-topic of complexity theory.

2,079 questions
Filter by
Sorted by
Tagged with
27 views

### Array Doubling Size Strategies

I would like to discuss resizing strategies for arrays please. If you have an array of $k$ initial size and it gets full, so you would like to choose from one of the following approaches: Approach 1: ...
12 views

### Calculating minimal discriminator of a set of columns in a matrix with unique rows

Having a matrix $M$, with unique rows, how to calculate a minimal subset of colums $D$ such that every row is unique? Also, how to maximize the amount of unique rows, if the number of chosen columns ...
25 views

### The interpretation of expected time bound for searches in a hash table

As CLRS book,page 260 stated, Thus, the total time required for a successful search is $\Theta{\left(2+\alpha/2-\alpha/2n\right)}=\Theta{(1+\alpha)}$ I wouldn't have any problem if the author says ...
20 views

### using TRIE for strings?

I saw the following question online: Init - Initlize data structure in O(1). Insert(s) - Add string s to your Data Structure in ...
15 views

### Average cost of insertion sort

I am confused how they get $\frac{n^2}{4}$ as average case of Insertion sort. Is it by testing every permutation of input and averaging the same input size then approximating the graph? If so how?
25 views

### A Query regarding Polynomial hierarchy collapse to a finite level [closed]

Assuming a hypothetical scenario that complexity class $PSPACE$ is shown to belong to complexity class $NP^{coNP}$ the Polynomial Hirerchy Collapses to a finite level. Query 1: Which level the above ...
28 views

### Efficient random sampling from large discrete distribution

I have a random variable $X$ that can take finite values in $\{X_1, ..., X_n\}$ with probabilities $\{p_1,..., p_n\}$. Is there a computationally efficient way to sample a number from this set? My ...
66 views

### Recurrence and Time complexity

I am having problem solving this recurrence. Can anyone help me with this please: $$T(n) = 2(T(\sqrt n))^2 , T(1) = 4.$$
Given a problem $E_0$ such that: Any valid solution $S_0$ if there is any is of polynomial length. Assuming we are able to guess the solution $S_0$, for it to be valid: i. There are a fixed set of ...