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
2answers
24 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
24 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
27 views

O(n^2) and O(nlogn) 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 perform ...
1
vote
3answers
77 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
15 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
18 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
14 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
22 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
32 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
37 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
17 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
38 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
60 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
29 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 ...
-2
votes
0answers
34 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
42 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
30 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
25 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
40 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
50 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
205 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
37 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
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
29 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
19 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
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
98 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
39 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
101 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
43 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
22 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
29 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
2 3 4 5
40