# 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,466 questions
Filter by
Sorted by
Tagged with
1 vote
5 views

• 121
70 views

### Possibly Tractable Variation of Suguru Puzzles

I'm currently investigating the computational complexity of a modified one-dimensional Suguru puzzle. The general Suguru puzzles were recently proven to be NP-complete (see here). My investigation ...
• 41
50 views

• 101
1 vote
86 views

### Perfect ordered hash function on ordered sequence

I have a sequence of integer tuples $t_1, t_2,..., t_N$ of different sizes in lexicographic order, e.g.: $(1, 1), (1, 2), (1, 3, 5), (1, 3, 6), (1, 5), (3), (3, 2, 3), (3, 7), (3, 8, 1), ...$ ...
40 views

### Which definition of decidable is correct?

Please note I don't use any of the "verifier" notation, I only concern definitions made with DTM and NTM . Now there are two definitions of decidability: 1. A set (predicate) is decidable (...
31 views

### Function / Algorithm that take fixed time to compute

I was wondering if there are any mathematical functions or algorithms that take a known minimum amount of time to calculate. The closest thing I could find to this is Proof of Work algorithms used for ...
• 129
38 views

### How $log((mn^2)!) = \theta (mn^2 log(mn))$?

Knowing that $log(n!) = \theta(nlogn)$
24 views

### Algorithms that depend on expected time and "regular" time complexities

Assume that I have designed an algorithm A, which runs two sub-methods: M1 and M2. M1 has a O($n$) expected time complexity. M2 has a O($n^2$) time complexity. Clearly A uses O($n + n^2$) = O($n^2$) ...
79 views

### Complexity of taking recursive modulo

Given 2 integer $M$ and $N$, a recursive modulo is $M \bmod (M \bmod (M \bmod ...(M \bmod N)$ until the result is 0. What is its time complexity? I guess that it's $O(log(M))$ but I can't prove it.
155 views

### Finding the time complexity of a prime factorization algorithm

In this question, I'm going to introduce a prime factorization algorithm which I'm working on as my personal project. I may attach a Python code to introduce the algorithm. If it contravenes the rule ...
35 views

### Does it make sense to apply path compression to kruskal algorithm?

I am reading about Kruskal and analysing it’s time complexity. Let’s say there are E edges and V vertices. Kruskal algorithm has two important time complexity equations , Sort edges- Elog(E) For ...
65 views

### Size and height of binary tree, different interpretations?

I can't seem to get my head around the formulas to use for size of binary tree. Depending on who I ask, what website, etc. I see different similar answers. So if someone could explain simply either: ...
39 views

### Derive complexity from recurrence relation

On the Wikipedia article on Karatsuba algorithm (https://en.wikipedia.org/wiki/Karatsuba_algorithm#Time_complexity_analysis) it is stated: $T(n) = 3 T(\frac{n}{2}) + cn + d$ And then, by invocation of ...
• 131
31 views

### In the complexity of open addressing, why it is necessary take the sum to $\infty$?

When estimating the average calculation complexity of open addressing, I found following explanation: Let $B$ be the number of backets and $N$ be the number of elements already in the hash table. The ...
• 1
1 vote
332 views

### Ordered sequence with logarithmic insert and remove

Problem: we have a sequence of numeric values, e.g. [102, 25, 77, 17, 2, 13]. We need to implement 3 operations, each can be at most logarithmic time complexity. <...
42 views

### Describing the set of Running Time of all Turing Machines

Consider the set of all valid Turing Machines descriptions $T_{All}$, and the set of functions that denote the real (not asymptotic) running time of Turing Machines in $T_{All}$, lets call it $R_{All}$...
• 23
1 vote
18 views

### Difference b/w Functional and Decisional Problem's computational complexity

I am trying to understand the difference b/w functional and decisional problems. The core as I understand is this: Functional Problems: Given an input $x$ we calculate some function $f(x)=y$ over it. ...
• 45
12 views

### Natural Problems not in P [duplicate]

From Time-Hierarchy theorem we know that there are problems that are not solvable in polynomial time. But I would like to know some natural problems that are provably not in P. Does anyone know a ...
1 vote
113 views

### Producing "moves" to permute one array to another

I have 2 arrays, A and B, which each contain the same N elements, but in a different order. (A different permutation) There are also no duplicates in A and B. I'm trying to devise an algorithm which ...
30 views

### Efficient Way to Calculate Timebased Followership

Problem A time based followship is defined as a person changing to a new job, and there is an existing employee there in the new company whom he used to work together. In this case, the old guy gets 1 ...
• 143
Consider a Turning Machine $A_0$ that takes two input parameters $(x, y)$ and its (exact not asymtotic) (polynomial) running time is given by $f(|x|, |y|)$ such that \$x^c < f(|x|, |y|) < x^{c+1}....