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

### Proof that there is a recursive language that is not decidable in $O(n)$ time

I having some trouble tackling an assignment. We're asked to prove that there exists a recursive language that's not decidable by a Turing machine in $O(n)$ time for inputs of length $n$. We're ...
154 views

### Highest useful complexity class

Aside from problems such as the halting problem, which aren't computable, are there any useful problems in computer science that can only be solved in time $O(2^{2^n})$, or in time $O((n!)!)$? I've ...
14 views

### Calculus of order of algorithm [duplicate]

I want to calculate the order of this function, I calculated but I'm not sure if this right. This is the function ...
49 views

### How to schedule different elements in a 24h range?

Given the following conditions: An element has: A time range, for example: 9:00 to 18:00. A repeat time, for example: every 5 minutes. Then a device recieves some elements and has to schedule them ...
69 views

### Find keys between $x$ and $y$ in binary search tree

Given $x$ and $y$, I want to find keys $k$ such that $x<k<y$, in a binary search tree. Can this be done in time $O(n + h)$, where $n$ is the number of keys between $x$ and $y$, and $h$ is the ...
225 views

### Complexity of active set method for Quadratic Programming

The Quadratic Programming problem is as follows: $$\min_x \{\frac12x^THx+x^Tg\}$$ $$Ax\le b$$ where $H$ is symmetric and positive semi-definite. What is the complexity of the active set method for ...
17 views

### Evaluate run time and compare these algorithms [duplicate]

Algorithm A divides the problem into 5 sub-problems of half the size. Solving each sub-problem then combining the solutions in linear time. Algorithm B solves problems of size n by dividing them into ...
56 views

### Why worst case running time of Insertion sort is $\Theta(n^2)$ [duplicate]

From Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein Theorem 3.1 For any two functions $f(n)$ and $g(n)$, we have $f(n) = \Theta(g(n))$ if ...
163 views

### What is the complexity of this recursive merge of two ordered Python lists?

This is not an assignment, but it is related to my Data Structures class. I just wrote this Python code to merge two ordered python lists. I do know that I could do something like this: list1 + list2....
622 views

### Algorithm analysis of nested loop [duplicate]

so I have this code: for (int i=1; i < n; i=i*5) for (j=i; j < n; j++) sum = i+j; And I'm wondering, what's the time complexity of this for ...
229 views

### Time-complexity of recursive defined code [duplicate]

How would I set up a recursive formula for time-complexity for this code: ...
10k views

### Time Complexity for matrix multiplication? [duplicate]

How can I find out the time complexity for the brute-force implementation of matrix multiplication for: Two square matrices ($n \times n$), Two rectangular matrices ($m \times n$) and ($n \times r$)?
4k views

### tightest upper bound on binary search tree insertion? [closed]

The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced What will be the tighter upper bound on this,will it become O(logn) I have read that ...
33 views

### Time complexity by solving recurrence relation [duplicate]

I was working on recurrence relation and came across this example T(n) = 2T(n/2) + log(n) What will be the time complexity, ie, big O for this relation. Thanks for any help in advance.
20 views

### Recurrence relation help? [duplicate]

$$t(n)=\begin{cases}n&\text{if }n=0,1,2,\text{ or }3\\t(n-1)+t(n-3)-t(n-4)&\text{otherwise.}\end{cases}$$ Express your answer as simply using the theta notation. I don't know where to go ...
82 views

### How to calculate Complexity Time O()? [duplicate]

Can anybody give me a way that i can use to calculate Complexity Time problems, i mean a way that will work on any complex code whatever it was. I can solve basic problems, but whenever the problem ...
32 views

### The use of master theorem appriopriately [duplicate]

I have a recurrence relation and trying to use master theorem to solve it. The recurrence relation is: $T(n) = 3T(n/5) + n^{0.5}$ Can I use the master theorem in that relation? If so, can I say that ...
868 views

### Time complexity of creating the unique binary tree from given inorder and preorder (or postorder) traversal sequences

Given inorder and preorder (or postorder) traversal sequences of a binary tree balanced binary tree binary search tree of n nodes, what is the time complexity of creating the respective unique tree.
135 views

### Graph Isomorphism variant

Question: Given 2 undirected graphs $G_1$, $G_2$, the problem whether exists a subgraph H1 of G1 which is isomorphic to a subgraph $H_2$ of $G_2$. What is the lowest complexity class for this problem: ...
880 views

### Determine nth prime number in O(?)

If f(n) is the problem to determine the nth prime number, how fast can this be done, i.e. What is the fastest known algorithm to find the nth prime number? What are lower bounds for the time ...
135 views

### Big O time complexity

I have a question if I have my $k=300$ and my loop is like this : for( int x = 0 ; x<n ; x--){ for(int y=0 ; y<k; y++){ ... } } Is this ...
56 views

### Time complexity of similar-looking functions

What is the time complexity of the following functions, and why? ...
128 views

### Big-O notation analysis [duplicate]

Can I get help to give an analysis of the running time Big-O? I'm not sure if all my answers are correct. I got for a) $O(n)$, b) $O(n^3)$, c) $O(n^{1/2})$ and d) $O(log(n))$ ...
176 views

### Proving an algorithm must have the lowest time complexity for sorting in the worst case

I'm curious if anything like this has been proved, or is even possible to prove a statement like: "Out of all sorting algorithms, this one has the lowest time complexity for the worst-case." Or ...
59 views

### Is this possible to find the maximum of differentiable and analytic function on finite and fixed interval in O(1) time using quantum computer?

$f$ is differentiable (continous) and analytic function. If $x\in\mathbb{R} \land 0\le x\le1$ then $f(x)$ is computable, $f(x)\in\mathbb{R}$ and $0\le f(x)\le1$. I have a conjecture that it is ...
60 views

### Quasilinear time algorithm for 3-SAT

Is it consistent with the current knowledge that there is an algorithm solving a 3-SAT instance in $n$ clauses in quasilinear time in $n$?
52 views

### Why 2^(2n+2) not equal to θ(2^2n)?

I'm trying to prove this expression 2^(2n+2) ≠ θ(2^2n)? Firstly 0 <= c1.2^(2n) <= 2^(2n+2) for this n=1 c1=1 is a solution set. For n = ∞, 0 <= ∞.c1 <= ∞ c1=1 is provide it. So omega ...
278 views

### Is that would be better approach to naive algorithm?

I was studying about naive pattern search algorithm and found that it requires two loops to match the pattern present in a string or not. That time an Idea stuck in my mind and I think it would be a ...
726 views

### Can we evaluate a polynomial of degree N modulo M at all M points, faster than Θ(mn) time?

Given a polynomial $P(x)$ of degree $N$, evaluate $P(x) \bmod M$ at $x = 0$ to $M-1$, where $M$ is a prime number of order $10^6$. Can we do any better than $O(NM)$ given the constraints we only need ...
197 views

### Scalar by N component vector multiplication faster than O(N)?

Is there a way to multiply scalar by vector faster than just multiplying each element of the vector by that scalar? It feels to me that there should be some exploit to do that. After all we will ...
2k views

### Proving that the complexity class $P$ is closed under union

The following is my proof for $P$ being closed under union. I wish to know if my proof is correct in addition to what it means for the union of two problems. Proof: Let $p_1, p_2 \in P$ Then by ...
44 views

### what is the time complexity of this for for for if

I need to know the analysis of time complexity of this case? ...
49 views

3k views

### Finding missing number in an unsorted array

You are given an unsorted array of all the integers in the range $0$ to $n = 2^k -1$ except for one integer, called the missing number. Find a divide and conquer algorithm to find the missing ...
2k views

### Computation complexity of an exponential function

How we compute the computation complexity of an exponential function like $a^x$ where $a,x \in \mathbb{Z}$ with $|a|=l$ bits and $|x|=m$ bits? Can anyone please explain using big notation?
101 views

### What is the Big O for n^2 + n * T(n-1) [duplicate]

I am working on the following algorithm time equation: T(n) = n^2 + n * T(n-1) What would be its Big O?
241 views

### What is the time and space complexity of the algorithm to either prove or refute that given expression is equals to (A+B)^n for any natural number n [closed]

Note that this is not duplicate of my previous question: how to simplify algebraic expressions, though it is similar, but still this is different, this is not the same. I need an algorithm that ...
394 views