# 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 [tag:runtime-analysis] instead. If your question concerns whether or not a computation will *ever* finish, use [tag:computability] instead. Time-complexity is perhaps the most important sub-topic of [tag:complexity-theory].

1,497 questions
Filter by
Sorted by
Tagged with
27 views

### Difference between a skiplist and an Indexable skiplist

Can someone please help me understand the main differences between a simple skiplist and an indexable skiplist? How does an indexable skiplist work in comparison to a normal skiplist (maybe a little ...
16 views

### CNF2 = { φ | φ is a satisfiable CNF-formula in which each variable appears at most 2 times}. Show CNF2 is in P

CNF2 = { φ | φ is a satisfiable CNF-formula in which each variable appears at most 2 times}. Show CNF2 is in P. I found this solution: We use the method of resolution to take the variables out ...
32 views

### Upper (or lower) envelope of some linear functions

Given some single variable linear functions $y_1=m_1x+b_1$, $y_2=m_2x+b_2$, $\ldots$, $y_n=m_nx+b_n$, the upper envelope is the function $f(x)= \max \{y_1, \ldots, y_n\}$. We know that this function ...
48 views

6k views

### Which Grows Faster: Factorial or Double Exponentiation

Which of the functions among $2^{3^n}$ or $n!$ grows faster? I know that $n^n$ grows faster than $n!$ and $n!$ grows faster than $c^n$ where $c$ is a constant, but what is it in my case?
30 views

82 views

### Can we solve this problem more efficiently than trying all possible combinations

Here is the context of the problem I am struggling with. I have a set of strings, for example: ...
43 views

### Find minimum pair number based on selection algorithm

If we have n balls in a red box (each ball is assigned a different number from 1 to n) and n balls in a green box (again each ball is assigned a different number from 1 to n). Lets say we have a ...
73 views

33 views

### How Expensive is Projecting onto a Polytope?

I have a problem where our action set is a polytope $\mathcal P\subset \mathbb R^d$ and an algorithm that involves projecting onto the action set. For example it says to select the Euclidean ...
53 views

### Linear sorting algorithm

I'm trying to understand sorting algorithms. And I'm thinking about a totally different way to tackle sorting: Use array indexes to sort a given set of integers. Suppose We want to sort a list of ...
28 views

### Is there any general, theoretical limit to time - space tradeoff?

In many algorithms, one can spot that improvements in time often are occupied by more memory requirements. For example usage of cache allows to speed up calculations by saving results in memory. Is ...
30 views

### Computing order statistics $1,2,4,8,\ldots,n$

On an array of $n = 2^k$ numbers, where $k$ is a non-negative integer, the $k = \log n$ order statistics $1, 2, 4, 8,\ldots, 2^k$ can all be determined in a total of $Θ(n)$ time in the worst case. I ...
13 views

### Detailed explanation of Perlin Noise algorithmic complexity

I am doing a project in analysis of algorithm and I have been looking all over for something more complex than Perlin Noise is $O(n \cdot 2^n)$ because of the doubling in $n$ dimensions and array ...
150 views

### Finding the hidden treasure

Let's assume I am trying to find a hidden treasure. The treasure is hidden at an uknown position x. We know that the position x of the treasure is somewhere on the integer axis (in other words x is ...
53 views

### Complexity of finding 7th smallest element in a min-heap? [duplicate]

I don't know if it's allowed to traverse nodes in a min-heap. Because, if traversal is allowed then for finding $7^{th}$ smallest element, only a constant number of nodes need to be checked, thus ...
41 views

### Time complexity described by recurrence relation

I need to find the time complexity described by the following recurrence relation. $T(n) = T(n/2) + T(n/3) + T(n/6) + n$ $T(1) = \Theta(1)$ The solution must be something like $T(n) = \Theta(f(n))$....
127 views

### How do you find a hash function that respects a custom equality function?

I've been tasked with hashing arbitrary types in C++, with the caveat that A == B implies hash(A) == hash(B) even if equality of ...
31 views

### Time complexity of recursive function

I am trying to find out how they calculated the time complexity of this small function . I am studying for an exam and found this question and the final answer is given, but I am trying to understand ...
Given $n$ sequences with length $m$, $s_i=\langle c_1^ic_2^i\dots c_m^i\rangle, i = 1,\dots, n$, where $c^i_j\in D$ is a partial ordered set and the partial order relation $\sqsubseteq$ on $D$ answers ...
I was studying for an algorithm exam and was having trouble answering (or rather proving) one of the practice problems. I want to find the correct symbol among $o$, $\omega$, $\Theta$ that would best ...