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
79 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
26 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 ...
0
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
57 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
39 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
38 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
21 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
vote
1answer
34 views

What is the “formula” for “any chipher can be deciphered by a quantum computer”?

There are several quantum complexity classes in different ways analogous to NP: NQP, QMA, and, as I understand, others. P=NP BPP=NP in simple words means "any cipher can be deciphered by a ...
2
votes
1answer
40 views

Is there a concept of probabilistic quantum computers?

Answering my question Yonatan N said a statement from which follows that there are computable functions of quantum time complexity strictly above polynomial. Accordingly a Quora answer Quantum ...
1
vote
1answer
72 views

Create binary numbers with a described pattern

I am looking for an algorithm that can create binary numbers following certain patterns. Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$...
-2
votes
1answer
57 views

recurrence relation for this n queen problem algorithm . and the time complexity

I am not able to understand how to write a recurrence relation for this n queen problem algorithm down below. Recurrence relation is for n*n board and the time complexity ...
1
vote
1answer
61 views

Is $𝑂(𝑛^{1/2}) = \Omega(𝑛^{\sin(n)})$?

As $-1 <\sin(n) < 1$, So $n^{\sin(n)}$ is bounded, but square root of $n$ tends to infinity. Is my logic correct? But from the other perspective, $1/n \leq n^{\sin(n)} \leq n$. I am confused.
0
votes
2answers
83 views

Does the O(n) algorithm always run faster than the O(n^3) algorithm? Why?

Assuming that the time complexity of the two algorithms $A_1$ and $A_2$ to solve the same problem are $O(n^3)$ and $O(n)$ respectively. If you write programs for these two algorithms and run them in ...
0
votes
0answers
47 views

How much faster are out machines (generally) than Arthur C. Clarke's machine in 1953's “The 9 Billion Names of God”?

In Arthur C. Clarke's short story, "The 9 Billion Names of God", two software/hardware engineers are contracted by a monastery to generate 9 billion string permutations from a 13-character ...
1
vote
1answer
53 views

Why do these functions satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n))?

I don't understand what these function are like and why they satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n)). Where is x? \begin{eqnarray} f(x)= \begin{cases} k^{2k}, &x\in(2𝑘,2𝑘+1)&...
0
votes
0answers
27 views

Implement Immediate Smaller Element problem using Stack

Immediate Smaller Element Problem: Given an integer array arr of size $n$. For each element in the array, check whether the right adjacent element (on the next ...
1
vote
2answers
91 views

Proving that a preorder traversal of a rooted tree can be performed in linear time

Definition: Let $T(V, E)$ be a rooted tree with root $r$. If $T$ has no other vertices, then the root by itself constitutes the preorder traversal of $T$. If $\lvert V \rvert > 1$, let $T_1, T_2, \...
1
vote
1answer
180 views

Is this clique algorithm in polynomial time correct or might it have another time complexity?

I came up with the idea finding a k-clique through starting at a small s-clique (like 1-,2- or 3-clique) and use it to find every s+1 Clique iterative. I had some trouble finding the Time Complexity ...
1
vote
1answer
19 views

How to express complexity of two functions considering it is the same in big O notation

I have two functions. a and b. Both have linear complexity O(n). ...
1
vote
1answer
16 views

Can inputs in the decision tree model be computed?

The Wikipedia definition of the decision tree model says that it allows the sign functions of certain classes to be computed in constant time (and presumably also memory). My questions, still ...
2
votes
2answers
60 views

Is $\log(n-1) \in \Omega(\log(n))$?

I saw this question Can I simplify log(n+1) before showing that it is in O(log n)? and wanted to know if a similar situation was also true. Namely, is $\log(n-1) \in \Omega(\log(n))$?
1
vote
1answer
182 views

Perfect matching problem

Suppose you are given two sets of integers L and M both having N elements. The problem is to match each number in L to a number in M. Such perfect matching has some cost given by $\sum_{i=1}^{N} l_i*...
1
vote
2answers
263 views

Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$

I'm trying to prove the running time of heapsort on an array sorted in decreasing/increasing order is $\Theta(n\lg n)$ in order to show that the worst-case running time of heapsort is $\Omega(n\lg n)$ ...
1
vote
1answer
333 views

Is the time complexity of the Fibonacci sequence O(fib(n))?

I started watching SICP lectures and am totally new to computer science. SICP. LEC 1B: Procedures and Processes; Substitution Model I don't know why the time complexity of the Fibonacci sequence is O(...
0
votes
1answer
18 views

What are the guidelines/tips for calculating the complexity of a chained-recursive function?

Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions.. Are there any ...
0
votes
0answers
75 views

Is time sharing an illusion?

I understand that every modern human made computer is being operated by time sharing operating systems which allow two or more users running two or more processes at once each, from two different ...
1
vote
0answers
37 views

Solving a recurrence relation with both decrementing and slicing the element by a constant

Given: $$f(1) = 1 \\ f(n) = 4f(n-1) + f(n/3) + f(n/8)$$ (if $n<1$ then it is still 1) And I need to find $\Theta(f(n))$, can I do this? $$ \Theta( f(n)) = \Theta(4f(n-1)) + \Theta(f/3)) + \Theta(f(...
1
vote
0answers
70 views

Covering Variation of Longest Common Substring

Given three binary strings, find the maximum possible length of a contiguous block of 1's formed by shifting and overlapping the strings. This may be interpreted as finding the maximum window size $k$...
1
vote
0answers
83 views

Need for Functions to be Increasing in Non-deterministic Time Hierarchy Theorem

I was going over the proofs of the non-deterministic time hierarchy theorem (the one in Arora-Barak and the one by Fortnow and Santhanam). They are available here: http://theory.cs.princeton.edu/...
2
votes
2answers
71 views

A double recursive function (ping-pong) between function to itself complexity analysis

def RecFunc(n): if n <= 3: return 1 return RecFunc( RecFunc(n/3) + RecFunc(n/2) + RecFunc(n/2) ) How should I start if it is nested inside? I know ...
1
vote
1answer
24 views

Algorithm for evaluating polynomials

I'm reading The Algorithm Design Manual and I stumbled upon this problem. I can't really get my head around this, I don't even know how the number of multiplications could differ, what I mean is that ...
1
vote
1answer
125 views

Partitioning list into two parts of almost equal sum

I was given this problem in class, and I have no idea how to solve it. The problem is: "Given a list of positive integers, divide the numbers into 2 groups such that the difference between the ...
1
vote
1answer
39 views

Proving big-theta complexity with constants in $f(n)$

I am working through a problem in which I have to prove that a particular $f(n) = \Theta(g(n))$. I know that for this to be true there need to exist positive constants $c_1$, $c_2$, and $n_0$ such ...
0
votes
1answer
72 views

What happens to the running time of an $O(n \ln n)$ algorithm if you double $n$?

Problem: Suppose the running time of a certain algorithm is $O(n \ln n)$. We happens to the running time of the algorithm if $n$ doubles. Answer: Let $R_1$ be the running time of the algorithm when ...
1
vote
2answers
43 views

How to analyse the time complexity of an algorithm based on the input values in addition to input size

I saw a joke on twitter today that got me thinking on how to perform a time complexity analysis of this algorithm such as you can express that the worst case is dependent on the input value in ...
1
vote
1answer
37 views

Does Master Theorem apply to $T(n) = 4T(n/2) + n^2 \log n$

Based on CLRS Theorem 4.1, master theorem doesn't apply to $T(n) = 4T(n/2) + n^2 \log n$. However, I saw the 4th condition of master theorem on slides of Bourke. If $f(n)=\Theta(n^{\log_ba}\log^kn)$, ...
1
vote
1answer
38 views

Queue FIFO search speed up through the change of visited array?

As I was preparing for the CCC this year, I am quite confused as to why a certain code modification was able to speed up my code for CCC Seniors Problem 2. Here was the C++ source code for my first ...
1
vote
0answers
19 views

Complexity of solving fractional constrained set multicover

Recently, I've encountered the following problem: Given a collection of sets $S_1 \dots S_n$ of elements $e_1 \dots e_k$ with element $e_k$ denoted privileged, and a $k-1$-vector $r$, choose at most $...
8
votes
1answer
731 views

why does LSPACE(log space) complexity class exist but not logtime?

I noticed that in complexity classes, logspace class is defined but there is no logtime. I was wondering how is that possible? Normally, I would expect the opposite, It is possible to do a search ...
4
votes
0answers
47 views

Simultaneous reachability of NFA states

Suppose I have a $n$-state non-deterministic finite automaton $F$ over alphabet $\Sigma$. Let $S(x)$ be the set of states reachable from the starting state by consuming string $x$. I am interested for ...
1
vote
1answer
57 views

Problems solvable in time $f(n)$ but not in time $o(f(n))$

Suppose I have some (increasing, nice asymptotics) function $f(n)$. Does there exist a complexity theoretic problem (e.g. PATH, 3-SAT, GO etc.) that can be solved in time $\Omega(f(n))$ on a ...
0
votes
1answer
55 views

Is big O notation additive?

For example, I have one program that requires $O(i)$ time complexity, and a second program requires $O(j)$ time complexity. Would the total time complexity be $O(i+j)$? And why?
0
votes
3answers
101 views

Computing square vs computing square-root? Time complexity

I am working on something that requires checking a very large natural number $x$ to determine if it is the square root of an even larger natural number $y$. So I am wondering what are the fastest ...
0
votes
1answer
26 views

Growth rate of roots vs logarithms

I'm trying to prove that the tenth root of n grows slower than the logarithms but I have no clue. Also, how can I find which of two functions grows faster? It it related to derivatives? Thanks a lot.
0
votes
0answers
14 views

Finding time complexity of a depth first traversal algorithm with a depth limit to get all node traversals starting from the root node

What would be the time complexity of a depth-first traversal algorithm on a graph, that is simply trying to retrieve all nodes being visited from starting node up until a depth limit is reached (i.e. ...
1
vote
1answer
319 views

Calculator for time complexity of recursive functions

Is there an online tool that returns the time complexity of recursion functions? For instance, when I enter $T(n) = T(n/2) + n$, I'd like to get $\Theta(n)$. I tried using Wolfram Alpha, but it doesn'...
1
vote
0answers
33 views

An opposite method of padding argument on N/DTIME complexity class

Is there a method to prove things with longer input in complexity theory? For example, using padding argument it's trivial to show that $\text{NTIME}(n^2) \subseteq \text{DTIME}(n^4) \Rightarrow \...
1
vote
1answer
55 views

Finding “entrance” points in a set of d-dimensional points. Can I do better than O(N^2)?

I am given a set of d-dimensional points, and need to find the set of entrance points in them. Definitions: A point p1 captures p2 if 1) All dimensions of p1 is smaller or equal to p2; and 2) At ...
1
vote
1answer
102 views

Time complexity and upper and lower bounds

Consider the following algorithm: (the print operation prints a single asterisk; the operation x = 2x doubles the value of the ...
-1
votes
1answer
52 views

Time complexity of similar-looking functions

What is the time complexity of the following functions, and why? ...

1 2
3
4 5
41