# 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
4k views

### How fast can we find all Four-Square combinations that sum to N?

A question was asked at Stack Overflow here: Given an integer $N$, print out all possible combinations of integer values of $A,B,C$ and $D$ which solve the equation $A^2+B^2+C^2+D^2 = N$. This ...
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 ...
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 ...
182 views

### Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi

We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work. ...
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 ...
17 views

17 views

### Solve recurrence where the base case's time complexity is a function of the original input size

I'm trying to analyse the time complexity of the following algorithm for generating the power set: ...
98 views

### $\Omega(m)$ and $O(m)$ meaning in theorem proof about dynamic array complexity

My algorithms and data structures' book states that to create a dynamic array the following procedure is followed: Let $d$ be the length of an array $a$ and $n$ the number of elements stored in ...
20 views

### Searching for sorting algorithm taking into account all possible solution of similar numbers

I need a reference for sorting algorithm where all possible orders are considered. example: if we have four values of n, and we do know there values n1(3) n2(5) n3(5) n4(10) and want to order them in ...
60 views

### How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time

This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani. Specifically, the problem statement is: Give a linear-time algorithm that ...
21 views

### Parameterized complexity of 3-SAT

Is the 3-SAT problem with $s$ variables and $t$ clauses FPT, parameterized by $s+t$, or W-hard, or para-NP-hard?
26 views

### Need the time complexity of this conditional statement method

My idea of the program is : Input = n sets objective function ObjFn equals to O(n^3) Output = the order of n sets Steps: Applying ObjFn to all n sets Choose the n of the Minimum ObjFn to be ordered ...
13 views

### Relation between time complexity and conditional statement [closed]

I need examples for the types of time complexity for conditional statement
20 views

### what is the running time of this while loop? [duplicate]

Hello i have a piece of code like this: ...
23 views

### Intuition behind : recursive algorithm takes exponential time [duplicate]

So I am studying an introductory chapter to dynamic programming that suggests a general solution to an optimization problem that occurs straightforwardly from expressing the problem with a reccurence ...
13 views

### recurrence equation 2T(n-4) + n^2 solution?

need help solving this equation. the general equation I end up with: 2^k * 2T(n-4k) + [ 2^k-1(n-4(k-1))^2 + 2^k-2(n-4(k-2))^2 + 2^k-3(n-4(k-3))^2....2^k-k(n-4(k-k))^2 ]
29 views

### Can a machine that, given infinite space, functions as a non deterministic turing machine actually exist in the real world?

I am a novice when it comes to computer science. But I know that traditional quantum computers are not non deterministic Turing machines. But it seems to me that the principles of quantum mechanics ...
72 views

### Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion

We know that the number of permutations possible for $n$ unique items is $n!$. We can uniquely label each permutation with a number from $0$ to $(n!-1)$. Suppose if $n=4$, the possible permutations ...
187 views

### Find two non-overlaping subarrays, with total sum equal to k

Given an array of N non-negative integers, and a number K, we need to find two non-overlapping contiguous subarrays that have a total sum of K. Our algorithm is supposed to find the minimum total ...
42 views

### What is the big-$O$ notation of a summation of logs where the arguments add to $n$?

For: $$\sum^{k}_{i=1} \log(x_i)$$ where: $$\sum^{k}_{i=1} x_i = n$$ Is there any big-$O$ result in terms of $n$ ? I found this, but is not what I'm looking for.
17 views

### What's the big O notation of this function and can you please explain why?

void RandIntArray(int arr[], int n) { int i, first, second, temp; ...
983 views

### Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?

I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
2k views

### Calculator for time complexity of recursive functions

Is there an online tool that returns the time complexity of recursion functions? For instance, when I enter $T(n) = T(n/2) + n$, I'd like to get $\Theta(n)$. I tried using Wolfram Alpha, but it doesn'...
36 views

51 views

### asymptotic tight bounds for quadratic functions

In Introduction to Algorithms by CLRS, it's said For any quadratic function $f(n)=an^2+bn+c$, where $a$, $b$ and $c$ are constants and $a>0$, $f(n)=\Theta (n^2).$ Formally, to show the same thing, ...
33 views

### References to deterministic time complexity of language classes

It's fairly well known that $REG \in TIME(n)$. I would like to know similar inclusions for the language classes $DCFL$ and $CFL$. I have found a variety of claims for these classes on the internet. ...
35 views

### Regularity condition for cases 1 & 2

My question concerns the version of the Master Theorem described in CLRS and in this handout. I already understand the following: If the regularity condition in case 3 does not hold, then we can't ...
1k views

### Time complexity of quicksort for arrays in increasing or descreasing order

Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order. Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using ...
9 views

### What is the time complexity of a Turing Machine that iterates through each prime number from 2 to K (assume oracle generates the next prime)?

Let NextPrimeNumber be an oracle that accepts a prime number n and returns the smallest prime number ...
23 views

### Hashing using chaining

In resolving collisions while hashing by chaining , if we store keys in the list in sorted manner, will we obtain any substantial performance in successful searches , insertion, deletion? What would ...
27 views

### How can I develop an algorithm to schedule production?

Given an an table that contains products I am selling with the dates, and given a table that contains the possible work orders with each work order, arrange the work orders such that all items are ...
21 views

### polynomial time approximation algorithm problem

How can we actually define a polynomial-time 4-approximation algorithm for vertex cover or knapsack problem? For say we have 2 approximation problems which less than equal 2C*. But when we have a ...
25 views

### What are the guidelines/tips for calculating the complexity of a chained-recursive function?

Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions.. Are there any ...
25 views

### Adversary argument and proving a lower bound of an algorithm. How does it work?

I need to understand how adversary argument works to prove the lower bound of an algorithm. For now, I am looking to prove that a "certain" algorithm that takes in input array requires omega(...
33 views

29 views

### best and worst case number of key comparisons of an algorithm

Consider the following algorithm: ...