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
27 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
36 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. ...
0
votes
0answers
16 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
36 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
11 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
45 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 ...
0
votes
1answer
26 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
33 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 ...
-2
votes
0answers
25 views

Time Complexity - Show that the set of perfect power belongs to P. Show that the rounded square root function belongs to FP [closed]

For this question, all numbers are represented in binary. You can assume without proof that the four standard arithmetic operations (addition, subtraction, multiplication, division with remainder) are ...
0
votes
2answers
32 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. Here's my logic to approach this problem, but I am ...
1
vote
1answer
27 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
19 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
24 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
28 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
39 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
49 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)$?
-5
votes
1answer
198 views

Is squaring easier than multiplication?

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
34 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 ...
0
votes
0answers
33 views

Time complexity of an algorithm that relies on convergence

I have trouble finding the time complexity of an algorithm that does the following: I have a set $S_1$ of $n$ documents which I search based on specific criteria: $O(n)$ complexity This leads to a set ...
1
vote
0answers
38 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
45 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
26 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 ...
0
votes
0answers
19 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
17 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
18 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
35 views
0
votes
0answers
8 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
92 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
32 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
40 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
38 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
39 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
98 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
42 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
26 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
4k 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
33 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
43 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
21 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
37 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 ...
0
votes
0answers
23 views

What is the complexity for the BFS algotithm for shortest path on unweighted grid?

What is the complexity of the BFS algorithm for the shortest path on the unweighted grid? The grid is a classical maze with a starting point and exit, need to find an exit. Can move only vertically ...
0
votes
0answers
47 views

Which of the following statement is true?

Given two statement: A:if inputs of a problem is online, then there is faster or equal algorithm in view of time complexity for that problem when input is offline. B:if inputs of a problem is offline, ...
1
vote
1answer
65 views

Can someone help me understand the time and space complexity?

Can anyone help me understand the time and space complexity here? I know zip() is O(1) and sorted() is O(n). The loop has the ...
0
votes
0answers
25 views

Hardness of finding all Control Flow Paths of a function

I have a control flow of function F, I want to know all control flows of this functions. I.e., function F { A; if B { B; } C; } would have the ...
-1
votes
1answer
38 views

Computationally and memory efficient algorithm for a relatively simple problem

Given a list of non-overlapping ranges and values, i.e. [(0, 5, 0.5), (10, 15, 1.1), ...], and a list of potentially overlapping ranges (bins), i.e. ...
1
vote
1answer
54 views

$O(n^2)$ running time vs $O(n^2)$ worst case

The use of the phrase "worst-case running time" is really confusing to me. Isn't plainly stating that the time complexity of an algorithm is $O(n^2)$ supposed to mean that the growth rate of ...
4
votes
1answer
36 views

Is there a linear-time solution to the minimum window substring problem, provided the characters in the substring must be in order?

Suppose there are two strings, $S$ and $T$, and we want to find the length $l$ of the shortest substring of $S$ which contains all the characters in $T$, in order. (Assume the length of $T$ is bounded,...
1
vote
1answer
34 views

Can the maximum single sell profit by divide and conquer be O(n)?

The single sell profit problem is: Given a list of prices on each day, find the maximum profit that could have been made by buying on one of the days and selling on a later day. There is a solution ...
1
vote
1answer
20 views

How to analysis the complexity of this LIS program?

I found a pseudocode online and I don't know why the complexity of it is $O(2^N)$, according to the site. Given a fixed curr, the for-loop in ...

1
2 3 4 5
39