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.

Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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....
0
votes
1answer
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 ...
0
votes
1answer
229 views

Time-complexity of recursive defined code [duplicate]

How would I set up a recursive formula for time-complexity for this code: ...
0
votes
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$)?
0
votes
1answer
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 ...
0
votes
0answers
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.
0
votes
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 ...
0
votes
0answers
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 ...
0
votes
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 ...
0
votes
1answer
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.
-1
votes
2answers
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: ...
-1
votes
3answers
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
56 views

Time complexity of similar-looking functions

What is the time complexity of the following functions, and why? ...
-1
votes
2answers
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))$ ...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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$?
-1
votes
1answer
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 ...
-1
votes
3answers
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
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 ...
-1
votes
1answer
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? ...
-1
votes
2answers
49 views

Big-O-notations and Small-o-notations

$a)$ Determine for all pairs $i$ and $j$, $i,j ∈ \{1, \ldots, 6\}$ whether for the ones given below functions $f_i ∈ O(f_j)$ or $f_i ∈ o(f_j)$ or neither of the two applies as $n → \infty$: $f_1 = \...
-1
votes
1answer
96 views

What is Simple Uniform Hashing, and why searching a hashtable has complexity Θ(n) in the worst case

Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the ...
-1
votes
1answer
476 views

turing machine accepting language {ww} has ω($n^2$)

prove or disprove that any turing machine which accepts language $l=\{ww | w ∈ \{0, 1\}∗ \}$ has time complexity $ω(n^2)$
-1
votes
1answer
83 views

what is the time complexity of this code

what is the time complexity of the following code. please help me. // a is mxn matrix ...
-1
votes
1answer
112 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 ...
-1
votes
2answers
60 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 ?
-1
votes
1answer
57 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) $...
-1
votes
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 ...
-1
votes
1answer
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?
-1
votes
2answers
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?
-1
votes
1answer
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 ...
-1
votes
2answers
394 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} {...
-1
votes
1answer
82 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.
-1
votes
1answer
92 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 ...
-1
votes
1answer
298 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, ...
-1
votes
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.
-1
votes
2answers
82 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 ...
-1
votes
1answer
292 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# ...