# 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,160 questions
Filter by
Sorted by
Tagged with
32 views

### OptFloodMax algorithms

For the OptFloodMax algorithm, either prove a smaller upper bound than O(n^3) on the number of messages or exhibit a class of digraphs and cot-responding UID assignments in which the ...
12 views

### A high-level call-by-reference question

First, let $H$ be a graph represented as an array of adjacency lists say. Next, let FindDegree$(H,y)$ be a standard subroutine that takes $H$ and a vertex $y$ in $H$ as input, and that returns the ...
17 views

### Complexity of insertion into a linked list, single vs double

At https://www.javatpoint.com/singly-linked-list-vs-doubly-linked-list, it says: In a singly linked list, the time complexity for inserting and deleting an element from the list is O(n). And: In a ...
14 views

### UCYCLE in LOGSPACE and linear time

Consider UCYCLE, the problem of recognizing undirected graphs containing a cycle. On the one hand, it's in LOGSPACE, see this stackexchange thread: start at every vertex $v$ a DFS and check whether it ...
44 views

### All possible sum of each array combination

Is there a name for this algorithm? I have an array {1,2,3} and all my possible sums are {1},{2},{3},{1+2},{1+3},{2+3}, {1+2+3} = {1},{2},{3},{4},{5},{6} {1,1,2} => {1}, {2}, {3}, {4} I tried to ...
17 views

61 views

### Complexity difference of Vertex cover and Vertex coloring regarding parametrized algorithms

I stumbled upon some problem in my understanding of the complexity classes FPT and XP. According to Wikipedia (and the Book "Parameterized Algorithms") we know the following about the Vertex ...
17 views

### Karatsube-Ofman runtime complexity computation

I have a question and didn't understand the solution, since we didn't take how to do it in the lecture and it's not explained in the solution sample. Question: One can generalize the Karatsube-Ofman ...
20 views

### Insertion Sort running time calculating using summtion

I was reading Introduction to algorithms, and stopped at the calculating the running time. For each $j = 2,3,..,n$ where $n = A.length$, we let $t_j$ denote the number of times the while loop test in ...
31 views

### Time complexity when loop index is an exponent

For any $n$ and any $x$, if one implements a loop to calculate: $$\sum_{i=0}^n x^i$$ What is time complexity of said loop if we assume $x^i$ to have time complexity of $O(i)$? What confuses me is the ...
67 views

Text: ...
32 views

### What is the time complexity of this code? can you explain in detail? [duplicate]

Consider the following code segment. Assume n to be a positive integer. ...
It is known that: $\Sigma_2^P \subseteq \Delta_3^P$ i.e. $NP^{NP} \subseteq \Delta_3^P$. $BPP^{NP} \subseteq \Delta_3^P$ If $\Sigma_2^P = PSPACE => BPP^{NP} \subseteq NP^{NP}$ Doesn't that imply: ...