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
1
vote
1answer
22 views

Can PTAS $\epsilon$ parameter be dependent on the algorithm input?

Let A be a PTAS algorithm with time complexity $O\left(\frac{1}{\epsilon}\right)$. Let $n$ be the input of the algorithm A. From Wikipedia: The running time of a PTAS is required to be polynomial in $...
1
vote
1answer
77 views

Is Vertex Cover of size $k >100$ polynomial time solvable?

I know that when we want to find out if Vertex Cover of size $k$ when $k \leq C$, belongs to P or not (when $C$ is some constant), we actually can find algorithm with polynomial time complexity (in ...
0
votes
0answers
108 views

Average number of comparisons for a successful search of a prime number in a binary search tree

A binary search tree is constructed by inserting the following value sequentially: $$3, 9, 1, 6, 8, 7, 10, 4, 2, 5$$ Let $p_v$ be the probability to search for the value $v$ in the binary search tree (...
-1
votes
2answers
45 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
vote
1answer
53 views

Time complexity of algorithms

I have some questions that I don't understand about time complexity. Given that the worst case complexity of the algorithm $A$ is $O(f(n))$ and the best case complexity of $A$ is $Ω(g(n))$. It ...
0
votes
1answer
46 views

$O(n^2)$ and $O(n\log n)$ exercise [duplicate]

There is an exercise which says : Al and Bob are arguing about their algorithms. Al claims his $O(n \log n)$-time method is always faster than Bob’s $O(n^2)$-time method. To settle the issue, they ...
1
vote
3answers
102 views

An $O(n^2)$ is faster than an $O(n\log n)$ algorithm for small $n$

If $n<100$ then $O(n^2)$ is more efficient, but if $n\ge 100$ then $O(n\log n)$ is more efficient. I am sure that this statement is valid, but I don't know how to prove it or justify it. Can ...
1
vote
1answer
20 views

Time complexity of finding median in data stream

I was reading a solution to the problem in the title on leetcode and the article says that the time complexity of the following solution is O(n) setup a data structure to hold stream value and insert ...
1
vote
0answers
22 views

Effect of determinization on the time complexity of Turing machines

Suppose I assume that the complexity of a non-deterministic Turing machine $N$ is $T(n)$, $n$ is the length of the input string. What would be the time complexity of a deterministic Turing machine $D$ ...
1
vote
1answer
15 views

can't quit understand one step of the recurrence time complexity calculation

I solved the question T(n) = T(sqrt(n)) + 1 but can't quit understand one step of the solution I don't understand the transition in (1). how did we conclude that T(m) = T(m/2) + 1 from the previous ...
0
votes
1answer
49 views

How to prove that one problem belongs to class P?

Is there any typical proving method when proving that one problem belongs to class P? For example, when proving that The problem of finding n to the kth power is the P problem. (Each multiplication ...
1
vote
1answer
38 views

Time-Complexity Verification: Code with two loops with an index halved at each iteration

I have the following code in python and was asked to find the tightest upper-bound in terms of Big-O , I've done two attempts below and I don't know which one is right, can you help me verify as to ...
0
votes
0answers
40 views

Complexity of backtracking to find power set given random array of numbers

Given an array of elements which can contain duplicates, this is an algorithm that solves the problem. ...
1
vote
0answers
19 views

Polynomial Time Complexity: O(loglog n) = O(n^2)? [duplicate]

Is O(loglog n) equal to O(n^2) in polynomial time? I know O(log n) is eqaul to O(n) in polynomial time because this can change as follows: log n > 2^(log n) > n^(log 2) > n. So, my question ...
0
votes
2answers
48 views

Time complexity of a function with while loop

What is the time complexity of the following procedure? for $x \in \{1,\ldots,n\}$: $\quad$ $i \gets \lfloor n/2 \rfloor$ $\quad$ while $i \neq x$: $\quad\quad$ if $i > x$ then $i \gets i -1$, ...
0
votes
0answers
16 views

Show that the set of perfect powers belongs to P [duplicate]

An integer n > 0 is called a perfect power if there are integers a, b ≥ 2 for which n = a^b. Show that the set of perfect powers belongs to P. Is the time complexity to this decision problem O(n^2)...
1
vote
1answer
64 views

Reducibility: Show that SUBSET SUM is reducible to the following problem A

A: Given nonnegative integers x1,...,xn (written in binary), and an integer k, can the net expenses be balanced using k or fewer checks? (Suppose that A is in NP). Purpose: to reveal that SUBSET SUM ...
-1
votes
1answer
39 views

Time Complexity: Does the following problem belong to NP?

Suppose n people live in a house and wish to share their expenses equally. Their respective expenses (before settling) are x1, ..., xn. They agree to write checks to each other so as to make all their ...
0
votes
0answers
45 views

Time Complexity: Show the following problem belongs to FP

Let $n > 0$ be an integer. Show that the rounded square root function $f(n) = ⌊\sqrt n⌋$ belongs to FP. Suppose $n=x+y$, where $x$ is the largest perfect square which is at most $n$, and $y$ is ...
0
votes
2answers
65 views

Consider a 1-tape TM that starts with n ≥ 1 written in unary/binary notation on its tape. Explain how it can count down from n to 0 in O(n) steps

Consider a 1-tape TM that starts with n ≥ 1 written in unary/binary notation on its tape. Explain how it can count down from n to 0 in O(n) steps. For binary notation, if we have a binary counter ...
1
vote
1answer
36 views

Time Complexity of Memoized Solution

I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on ...
1
vote
1answer
23 views

Theta bound for runtime analysis of nested while loops

I am trying to fully analyze the running time of $\texttt{nestedLoops}$ in terms of $n$ with a Theta bound. The Java code I have is as follows: ...
0
votes
1answer
42 views

Is the multiplicative constant in the Big O notation are ignored because of Linear Speed-Up theorem?

I just want to know if Big O notation was used as a consequences of the Linear speed up theorem or not. For me I guess the answer is yes. For example, if we didn't have a linear speed-up theorem, then ...
0
votes
2answers
30 views

Can quantum computers be modelled as a classical computer with access to an oracle?

Quantum computers can solve certain problems faster than classical computers e.g factoring numbers. and this is because quantum computers can do a fourier transform on $n$ bits in $O(n^2)$ time as ...
2
votes
0answers
50 views

Two dimensional recursive function in $O(\log n)$ time complexity

It is well known that a recursive sequence or $1$-d sequence can be calculated in $O( \log n)$ time given that it has the form $$a_n=\sum_{k=1}^{n} C_ka_{n-k},$$ where $C_k$ is a constant. Examples ...
1
vote
1answer
88 views

Running time of heap sort, when all number are identical

Given n numbers that all are identical, then what would be the running time of heap sort? Will it be in linear time $O(n)$ or, best case $\Theta(n\log n)$?
-4
votes
1answer
242 views

Is squaring easier than multiplication? [duplicate]

Let $T_1(n)$ be the time complexity of computing the square of an $n$-bit integer, and let $T_2(n)$ be the time complexity of computing the product of two $n$-bit integers. Assuming that addition is ...
0
votes
0answers
39 views

O(nlogn) or O(n) alternative for Needleman-Wunsch algorithm

So I am a computer science student and I was recently looking at the subject of comparing DNA sequences. Probably the most widely used algorithm is the Needleman-Wunsch algoirithm and while it might ...
1
vote
0answers
41 views

Optimize binary multivariate polynomial multiplication

You have a few variables that can only assume the values 0 or 1 and you use those to form two polynomials. Is there a way to multiply the two polynomials that is faster than O(n²) where n is the ...
0
votes
1answer
65 views

How to find i largest numbers in unsorted array in O(n) where i <= n^(1/2)

If we have length $n$ unsorted array such that each element is integer and different, how to find $i$ largest numbers in linear time O(n)? but $i \leq n^{\frac{1}{2}}$. For example, if we have $A = [...
1
vote
1answer
39 views

What are string matching algorithms used in text editors like Atom and sublime

I know there are many algorithms for finding a pattern in a text like Boyer Moore, KMP, RabinKarp and so on. I want to know what is the one that is mostly prefered by text editors and IDEs, as I find ...
-1
votes
1answer
45 views

What will be the frequency count of this code snippet?

int i=0,j; while(i<=n) { while(j<=(i+1)){ a=a*a; j++; } i++; This question was in my homework and we have to calculate the frequency count of the ...
0
votes
0answers
21 views

Polynomial reduction, #P-hard problems, and approximations

Consider two statements. Statement 1: The problem #3SAT (finding the number of satisfying instances to a 3SAT problem) is #P-hard. Statement 2: Additively approximating #3SAT upto $\pm 2^{n/2}$ error ...
0
votes
0answers
19 views

Recurrence relation of an algorithm

how can I know what are the recursive calls of this algorithm ? in line two there are 2 recursive calls and I don't know how to write this as T(n) for the Recurrence relation. Here is the algorithm :
1
vote
2answers
41 views
0
votes
0answers
10 views

solving 𝑇(𝑛)=𝑇(𝑛/3)+𝑇(𝑛/6)+1 without Akra-bazzi method [duplicate]

I need to find $g(n)$ so that $𝑇(𝑛)=𝑇(𝑛/3)+𝑇(𝑛/6)+1 = \Theta(g(n))$. I know that the recursion tree height, $h$, is $\lg_6{n}\le h \le \lg_3{n}$ and that every level of the tree has at most $2^d$...
1
vote
1answer
198 views

Time complexity of the following the code for(i = 1; i<=n;i++){for(int j=i+1;j<n-i;j++)}

for(int i = 1;i<=n;i++){ for(int j = i+1;j<=n-i;j++){ print("hello"); } } The first loop has time complexity of n and ...
1
vote
1answer
36 views

What's the time complexity of this function?

Consider the below function: Considering that print(a) and swap(a, b) are of complexity $\theta(1)$, what is the time ...
1
vote
1answer
19 views

Which of the following is a more appropriate complexity for this reccursive function?

Given the following recurrence relation: \begin{gather*} h(A) = \begin{cases} 0,\qquad \qquad \text{ }\text{ }\text{ }A=0\\ 1+h(A-1),\text{ }\text{ }A\text{ is odd} \\ 1+h(\frac{A}{2}),\...
2
votes
1answer
57 views

How does knowing the input size make the time complexity of a function constant?

After reading the question and answers on Time complexity of min() and max()? I would like to clear up some confusion on the relation between time complexity and size of input. First, I've noticed ...
2
votes
1answer
46 views

Binary exponentiation of matrix - complexity

I want to calculate complexity for binary exponentiation of matrix of size $k$. Let's say that I'm using the simplest approach to multiply matrices (so with three ...
0
votes
0answers
41 views

How many times whille loop will be executed when we double the value?

Consider this loop: for i = 1 to n j = i while j < n j = j + j end while end for How many times the while loop will ...
5
votes
1answer
180 views

Algorithms for almost sorting

I want to find a comparison sorting algorithm that can almost sort a set of data, using the least comparisons possible. What I mean by "almost" is that if the perfectly sorted data is $[x_1, ...
0
votes
0answers
59 views

Prove or disprove $T(n) = T(\lfloor\frac{n}{2}\rfloor+1)+1=O(\log(n))$

Lets define function $T(n)$ as \begin{align*} T(1) &= T(2) = 1\\ T(n) &= T(\lfloor\frac{n}{2}\rfloor+1)+1 \text{, where }n\ge 3.\\ \end{align*} Does $T(n)=O(\log(n))$? I have no idea how to ...
0
votes
1answer
42 views

How will Big O be with quantum computers?

I don't even know if this is the right place to ask this this...but how will Big O be with quantum computers? More specifically, will the worst case always be constant? If yes, how will this change ...
7
votes
12answers
7k views

Time complexity of min() and max() on a list of constant size?

If you use min() or max() on a constant sized list, even in a loop, is the time complexity O(1)?
1
vote
1answer
39 views

Doubt in understanding the time complexities of algorithms to recognize regular expressions

I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al first edition where I came across the following table. The authors justify the table as follows: Given a ...
2
votes
2answers
46 views

How to solve recursion T(n) = T(n/3) + T(2n/3) + n?

$T(n) = T(n/3) + T(2n/3) + n$ How can I solve this recurrence formula?
0
votes
0answers
25 views

Order-statistic tree: Worst-case running time of a sequence of $n$ insertions/deletions and $m$ calls to SELECT operation

Assume I have an order-statistic tree, $T$, which is a red-black tree where every node $x$ also has the attribute $x.size$. How can I compute the worst-case running time of an arbitrary sequence of $n$...
1
vote
1answer
38 views

Can someone help me fully grasp idea and time/space complexity with this code?

My understanding is the following: Time = With the initial not state is just to check if there are no elements in the list a. This is done in O(1) time. The first ...

1 2
3
4 5
41