# 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,569 questions
Filter by
Sorted by
Tagged with
67 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 ...
175 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 ...
51 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 ...
162 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....
571 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 ...
1k views

What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$? So far I have: $O(n) \le cn$ for some constant $c$ Hence: $$T(n) \le 3T(\frac{n}{2}) + cn$$ After a recursion: $$T(n) \le ... 1answer 164 views ### Time-complexity of recursive defined code [duplicate] How would I set up a recursive formula for time-complexity for this code: ... 0answers 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)? 1answer 3k 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 ... 0answers 32 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. 0answers 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 ... 0answers 81 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 ... 0answers 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 ... 2answers 277 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 ... 1answer 608 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. 2answers 92 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: ... 3answers 642 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 ... 1answer 133 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 ... 2answers 107 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)) ... 1answer 119 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 ... 1answer 58 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 ... 3answers 217 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 ... 1answer 642 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 ... 1answer 96 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 ... 1answer 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 ... 1answer 39 views ### Solve recurrence with Master Theorem - Polynomially Smaller/Larger The problem is to solve the recurrence using Master Theorem :$$T(n) = 2T(n/2)+\log_2 {n}$$My attempt:$$ a=2, b=2, f(n)= \log_2 {n}, g(n)=n^{\log_b{a}}=n $$I am torn between case 1 & the ... 1answer 43 views ### Time complexity of removing duplicates in lists Question I am wondering what is the minimum time complexity of get the unique value of a array in two conditions: keep the order or not. For example, suppose we have a original array ... 2answers 22 views ### Units of time in time analysis (frequency count method) In time analysis, how many units of time will the piece of code z=2x+3y; take? will it take 1 unit of rime or 4 units of time ? 1answer 43 views ### confused with Time Complexity [duplicate] I was reading book related to Time Complexity, and came up with 4 lines of equations that I could not understand properly, could you please explain why are those true? 1) n = o(n\log\log n) 2) ... 2answers 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 ... 2answers 97 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? 1answer 197 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 ... 2answers 268 views ### Solve using master method T(n) = n · T(n/2) + n^{\log n} [closed] T(n)=n\displaystyle \cdot T\left(\frac{n}{2}\right)+n^{\log_{2}n}. f(n) = n^{\log_{2}n} Number of leaves = n^{\log_{a}b} = n^{\log_{2}n} CASE 2 (All level same) f(n) = \Theta(n^{\log_{b}a} {... 1answer 60 views ### Give a function that is in EXPTIME but is not in O(2^n) [closed] Give a function that is in EXPTIME but is not in O(2^n). Thanks. 1answer 91 views ### How fast can one compute the power of a number? Let x \in \mathbb{R} and k \in \mathbb{Z}^+ \cup \{0\} then how fast can one compute x^k? If x, k \in \mathbb{Z} then I guess this previous discussion already settled that, How many ... 1answer 210 views ### Problem in computational complexity (superior class) Say that a class C_1 is superior to a class C_2 if there is a machine M_1 in class C_1 such that for every machine M_2 in class C_2 and every large enough n, there is an input of size ... 1answer 187 views ### Is the complement of the given language necessarily in NP? A is a given language so that A \in NP. Assume that P = NP. Is A' necessarily in NP? What I did: A \in NP , P=NP P=coP (Can be proven by running a TM M as a decider for P, ... 1answer 16 views ### Use of Landau notation for determining bounds [duplicate] Assume that we have l \leq \frac{u}{v} and assume that u=O(x^2) and v=\Omega(x). Can we say that l=O(x)? Thank you. 2answers 78 views ### Is there a computation that takes the same amount of time to run on any computer? [closed] I'm looking for research that has been done towards finding types of computations that take the same exact amount of time to run, regardless the amount of computing power one has. I've been thinking ... 1answer 216 views ### What's the time complexity of this append method? [closed] I made a method that appends a sequence to another sequence. So: (append [1,2,3] [4,5,6]) = [1,2,3,4,5,6] CODE In C# ... 1answer 29 views ### Complexity of while loop Average,Best,worse case ... 1answer 123 views ### All the possible inputs for a given AVL tree Given an AVL tree,what are the possible inputs so that the same given tree is formed(please dont mention brute force technique)? 1answer 76 views ### Measuring infinite loops [closed] Theoretically, is there a way to measure how many infinite loops are running at a given point in time? In other words, is there a way to freeze everything and get a number on how many infinite lines ... 1answer 68 views ### What will be the computational complexity of a system with two pipelined algorithms? A system consists of two separate algorithms (operated in pipeline). Algorithm#1 is iterated m times and has a time complexity ... 1answer 512 views ### Binary search trees: multiple Successor() calls Show that, given a tree node a, the time complexity of calling k times to Successor() is O(k+h), where h is the tree height. ... 1answer 615 views ### Running time of amstrong algorithm I have a problem how to find best, worst, average case in armstrong number algorithm? Here the pseudo-code : ... 1answer 264 views ### A difficult master theorem problem Consider the function B:\mathbb{N}\rightarrow\mathbb{R} defined by$$ B(n) = \begin{cases} 1 &\text{if $n\le 2$}\\ B\left(\left\lceil\frac{n}{\log_2n}\right\rceil \right)+n&...
Is it possible to delete duplicates from a sorted array in $O(\log N)$ time and $O(1)$ space?