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
4 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 ...
4
votes
2answers
277 views

Polynomial-time linear-reduction from Directed Hamiltonian Path Problem to 3SAT

Is there a polynomial-time reduction from Directed Hamiltonian Path Problem to 3SAT which is linear in the number of vertices? That is, it reduces every directed graph $G$ with $n$ vertices to a ...
1
vote
1answer
53 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.
-1
votes
2answers
60 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 ...
6
votes
1answer
5k views

What is an optimal algorithm?

I'm a computer science newbie and I thought I understood cases and bounds when I first studied them. I would take worst case as upper bound and best case as lower bound, but now I know that they are ...
1
vote
1answer
50 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
42 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 ...
0
votes
0answers
24 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
1answer
169 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
2answers
83 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
2answers
99 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
18 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). ...
2
votes
2answers
44 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
14 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 ...
1
vote
1answer
60 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
1answer
86 views

Runtime of weighted interval scheduling dynamic programming algorithm

Consider this implementation of a dynamic programming algorithm for weighted interval scheduling: ...
1
vote
1answer
305 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
16 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 ...
8
votes
2answers
4k views

Is “super-exponential” a precise definition of algorithmic complexity?

I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity. For instance, if an algorithm runs for $nC(n-1)$...
0
votes
0answers
73 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
79 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/...
1
vote
0answers
67 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$...
2
votes
2answers
68 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 ...
0
votes
1answer
39 views

Making an algorithm that picks a unique random number in fixed set more efficient

I have been working on a project that simulates an online bank. At this point, I'm implementing the code used to create user accounts. Each account will have a sortcode and account number, I have ...
1
vote
1answer
46 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
20 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 ...
0
votes
2answers
52 views

Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$

Prove by induction that $T(n)=\Theta(n^2 \log_{3}n)$ where $$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$ The base case for $n=1$ seems ...
1
vote
1answer
65 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
1answer
35 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 ...
1
vote
2answers
38 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
26 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)$, ...
2
votes
1answer
38 views

Clarifying the definition of reduction with regards to NP-complete problems

In my logic class we started learning about the different complexity classes. In particular, we focused on the NP complexity class. A problem is in NP if it is solvable in polynomial time using a ...
1
vote
2answers
225 views

Does DFS have better constants/complexity than Backtracking on a Graph?

I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step ...
1
vote
1answer
37 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 ...
0
votes
1answer
93 views

Time complexity of a 2-heap question

The problem statement is pretty straight forward: given an array of integers and a window size, return an array of doubles of the median of each window. arr = 1, 3, 5, 10, 6, 9, 2 k = 3 would yield ...
1
vote
1answer
68 views

What is the time complexity of FC_MRV algorithm?

I am studying CSP and read the papers on it.I wanted to know the time complexity of Forward checking with Minium Remaining Value algorithm.
1
vote
0answers
17 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 $...
7
votes
1answer
689 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
34 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
53 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
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
3answers
87 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 ...
3
votes
1answer
92 views

Complexity of “Fast Poisson Disk Sampling in Arbitrary Dimensions”

I came across the paper Fast Poisson Disk Sampling in Arbitrary Dimensions which gives an algorithm for generating Poisson disk points in $\mathbb{R}^n$. It's claimed that the algorithm is linear ...
0
votes
1answer
38 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?
1
vote
0answers
30 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 \...
0
votes
2answers
45 views

Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem

I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$ with base case $T(n) = 1$ if $n \leq 1$. I know that the solution is(with the help of the Master Theorem) $$\...
5
votes
3answers
12k views

Time Complexity of Rabin-Karp matching algorithm

I asked a question on Rabin-Karp Searching algorithm here, which I am reading from the book "Introduction to Algorithms" 3rd edition Cormen et al.. After reading few para of the section on ...
0
votes
1answer
24 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.

1
2 3 4 5
38