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 [tag:runtime-analysis] instead. If your question concerns whether or not a computation will *ever* finish, use [tag:computability] instead. Time-complexity is perhaps the most important sub-topic of [tag:complexity-theory].

Filter by
Sorted by
Tagged with
2
votes
1answer
60 views

What is the Time complexity of $\sum_{i=1}^n 1+\lfloor\log_2 i\rfloor$

What is the time complexity of $$\sum_{i=1}^n 1+\lfloor\log_2 i\rfloor$$ and how do you calculate it?
0
votes
0answers
26 views

Prove that exists PARITYn fuction with size O(n^2)

Have to find Boolean circuit formula that solves PARITYn problem with complexity O(n^2)? (Function PARITYn(x1, . . . , xn) is equal to 1 if and only if the number of variables x1, . . . , xn equal ...
0
votes
0answers
20 views

Question about asymptotic analysis comparing two functions

I'd be glad for an explanation on the analysis of this exercise. Given these functions: $$f(n) = n^2 \\ g(n) = n^{2/3}$$ Show that $f(n) = O(g(n))$, or $f(n) = \Omega(g(n))$ and comment if $f(n) = \...
-1
votes
1answer
39 views

Solve recurrence with Master Theorem - Polynomially Smaller/Larger

The problem is to solve the recurrence using Master Theorem : $$T(n) = 2T(n/2)+\log_2 {n}$$ My attempt: $$ a=2, b=2, f(n)= \log_2 {n}, g(n)=n^{\log_b{a}}=n $$ I am torn between case 1 & the ...
11
votes
2answers
2k views

Is there a name for the class of algorithms that are the most efficient for a particular task?

This would be analogous to the Kolmogorov Complexity of a string, except in this case, I'm interested in the algorithm that solves a given problem using the least number of steps. We would therefore ...
1
vote
1answer
42 views

Is there a defined set of steps or principles on how to reduce time complexity of algorithms?

I have been watching some big (Google, Facebook,..) company interview examples and usually when pair programming, they develop the most straightforward algorithm and then the interviewer asks 'could ...
1
vote
1answer
23 views

Is the sieve an improvement for prime finding over an optimized algorithm?

I don't think it is, as you have to loop through each set multiple times at least. implementation of sieve in JS - in the answer at the bottom. The link shows a 10X improvement using sieve. In this ...
0
votes
0answers
15 views

Prove that a set is decidable using time constructible function

I'm preparing an exam of theory of computation and I'm very in trouble with some exercise. Considering a Turing machine $\mu$ of alphabet $A=\{ 0,1 \}$ (we don't know nothing about termination) and a ...
0
votes
1answer
29 views

Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi

We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work. ...
0
votes
1answer
15 views

Asymptotic growth of a function containing a sum

How to compare the asymptotic growth of a function containing a sum with another function? I'm not sure how I'm supposed to dissolve the sum. Usually I just take the limis of f(x)/g(x). If that fails ...
1
vote
1answer
58 views

Time complexity of $O(n)$ loop which has a multiplication ($O(n^2)$) in it

Assume we know that the implementation for the multiplication operator for a language is known to be $O(n^2)$. Given this pseudocode: ...
-3
votes
0answers
38 views

Time and Space Complexity

Write pseudo code to compute ⌈log2 n⌉ given any pos- itive integer n ≥ 1. What is the time and space complexity of your algorithm using RAM uniform cost model ?
1
vote
1answer
45 views

Recurrence relation and time complexity of recursive factorial

I'm trying to find out time complexity of a recursive factorial algorithm which can  be written as:   fact(n) {  if(n == 1)  return 1;  else  return n*fact(n-1)  } ...
0
votes
1answer
25 views

How will I calculate the time and space complexity for this pyramid algo? [duplicate]

This is an algo. programmed for displaying a letter pyramid if the buildPyramids() method is passed argument str, i.e. "12345": ...
3
votes
1answer
96 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 ...
0
votes
0answers
36 views

Binary Search Complexity

I was reading an article about Binary Search on one of the websites on the internet that someone had linked, can't find the link anymore, but this really is bothering me, and I think I am missing ...
2
votes
2answers
82 views

Algorithm to compute $n^{\log k}$ in $O(\log\log k)$

I was given this exercise and I think I have to use a variation of Gauss repeated squaring, but I can not figure out how to produce $\log\log k$ in steps, like when you divide $k$ by $2$ to compute $\...
-1
votes
1answer
42 views

Time complexity of removing duplicates in lists

Question I am wondering what is the minimum time complexity of get the unique value of a array in two conditions: keep the order or not. For example, suppose we have a original array ...
2
votes
3answers
68 views

Time complexity - Algorithm to find the lowest common ancestor of all deepest leaves

This is the problem statement I came across today. Given a binary tree, find the lowest common ancestor of all deepest leaves. I came up with a correct algorithm, but I would like to confirm the ...
1
vote
0answers
22 views

Time complexity of a hybrid merge and selection sort algorithm

I'm trying to analyse the time and space complexity of the following algorithm, which is essentially a hybrid of a merge and selection sort. The algorithm is defined as follows: ...
0
votes
0answers
37 views

What can be said about complexity class of a problem if there exist a pseudo-polynomial verification algorithm?

Let X be a problem for which pseudo-polynomial algorithm time for verification of solution exists. What can be said about complexity of problem X? Can X belong to NP-hard class?
1
vote
1answer
27 views

Runtime of weighted interval scheduling dynamic programming algorithm

Consider this implementation of a dynamic programming algorithm for weighted interval scheduling: ...
2
votes
0answers
26 views

Can every node of a link/cut tree be accessed in $O(n)$ time?

Per the Sequential Access Theorem we can access every node of a splay tree in $O(n)$ time, when accessing the nodes in a specific order. Given a link/cut tree, is it possible to access all of its ...
3
votes
2answers
46 views

Why is $O(|V| + |E|)$ the bound on DFS and BFS instead of just $O(|E|)$?

In one sense I understand why the bound on BFS and DFS is $O(|V| + |E|)$. Every vertex gets considered, hence the $O(|V|)$, and over the course of considering all adjacent vertices, we end up ...
0
votes
1answer
21 views

Uniqueness of non-dominated two-dimensional points

This question is a nice variant of How to compare n number of m-dimensional points among one another with minimum time complexity? for two dimensions. We say point $p_i=(x^i_1, x^i_2)$ dominates ...
2
votes
1answer
54 views

NP-completeness of a problem with pretty fast algorithm

Supposing if a problem with $n$ non-deterministic bits is in $O(2^{\alpha n})$ time at every $\alpha\in(0,1)$ then is there evidence that problem can or cannot be $\mathsf{NP}$-complete?
3
votes
0answers
22 views

Bit complexity of computing the sign of an expression evaluated at an algebraic number

I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of ...
1
vote
1answer
61 views

PTAS vs. FPTAS input

I am trying to understand what is the PTAS, FPTAS and what is the difference between them. I found this analysis: PTAS definition vs. FPTAS but I cannot understand what do we mean by saying: ".......
2
votes
1answer
103 views

How to compare n number of m-dimensional points among one another with minimum time complexity?

Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all ...
2
votes
0answers
24 views

planar max cut graph with constrains

Given a planar graph $G=(V, E)$ I am looking for a max cut algorithm with the following conditions : some vertices are in one of the partition sets? Is the algo is still polynomial ? I mean a ...
2
votes
1answer
33 views

Coloring a graph with odd number of vertices with $k$ (which is close to $\Delta$) colors in linear time

We have an undirected simple connected graph with odd number of vertices. We also know the number $k$ which is actually the closest odd number greater than or equal to $\Delta$. (So if $\Delta$ is ...
0
votes
0answers
20 views

Quick Clarification Question about Time Complexity in CLRS

I'm reading about the Hiring Problem in "Introduction to Algorithms" and read Interviewing has a low cost, say $c_i$, whereas hiring is expensive, costing $c_h$. Letting $m$ be the number of ...
2
votes
1answer
33 views

What's the decoding time complexity of LT codes?

LT codes are practical fountain codes that are near-optimal erasure correcting codes. Simply stated, for encoding a $n$-block message, each packet first chooses a degree $d\in\{1,\ldots,n\}$ ...
2
votes
1answer
50 views

Time complexity of algorithm inversely proportional to size of sub problem?

Let's say I have an algorithm with time complexity $T_n = T_\frac{n-1}2 + 1$, $T_0 = 0, T_1 = 1$. Assume (Induction hypothesis) $T_n = C\log_2(n+1)$ for some $C$. $T_1$ imposes $C \geq 1$. Therefore ...
1
vote
1answer
51 views

Time complexity of combinations of n pairs of parentheses

I have the following code snippet for combinations of n pairs of parentheses. ...
0
votes
0answers
28 views

What is the run time of this algorithm, written in pseudocode?

count = 0 for i = 1 to n: for j = 1 to i: count += 1 So from my understanding, we can break this up into 2 summations, by nesting the $j$ loop as a ...
3
votes
1answer
46 views

Fastest algorithm for transforming points into graph

Given a set of $n$ two-dimensional points in the plane $$\{ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\}$$ and a real number $M$, I want to transform this set of points into a graph with the points as ...
3
votes
1answer
64 views

Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$

Given two algorithms with their time-complexity $t_a(n)=\sqrt{n}$ and $t_b(n) = 2^{\sqrt{\log _{2}n}}$ and i have to show $t_b(n) = O(t_a(n)) $. I´ve made a program to check this statement and it ...
0
votes
1answer
58 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 ...
3
votes
1answer
116 views

Compare two complexity functions having the same asymptotic complexity

For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found: $A1: T_{A1}(n)=4n^2 +7log(n^2)$ $A2: T_{A2}(n) = 4T(n/2) + log(n)$ Say, technically ...
1
vote
0answers
35 views

Which function grows faster: N Log N or N^(1+ε/√(log N)) [duplicate]

How would you go about solving this problem? I thought about using a limit infinity approach, but got confused and Wolfram Alpha didn't provide any explanation.
2
votes
1answer
60 views

Are problems in NP $\cap$ coNP less difficult than those in NP-complete?

I am taking a complexity class now, and I struggle to understand the concept of "hardness": Assume that $L \in \textsf{NP } \cap \textsf{coNP}$. In means that under the assumption $\mathsf{NP} \neq \...
-1
votes
2answers
22 views

Units of time in time analysis (frequency count method)

In time analysis, how many units of time will the piece of code z=2x+3y; take? will it take 1 unit of rime or 4 units of time ?
4
votes
1answer
102 views

Improving time complexity from O(log n/loglog n) to O((log ((nloglog n)/log n))/loglog ((nloglog n)/log n))

Suppose I have an algorithm whose running time is $O(f(n))$ where $f(n) = O\left(\frac{\log n}{\log\log n}\right)$ And suppose I can change this running time in $O(1)$ steps into $O\left(f\left(\...
0
votes
1answer
55 views

Understanding $O(2^n)$ time complexity due to recursive functions

Consider the following binary recursive fibonassi program: ...
0
votes
1answer
31 views

how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$

how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then ${NP = P ? }$
0
votes
1answer
75 views

How to get Algorithm complexty based on another 2 algorithms?

I had quiz last week and it says: suppose algorithms $A_1$ and $A_2$ have worst-case time bound $p$ and $q$, respectively. Suppose algorithm $A_3$ consists of applying $A_2$ to the output of $A_1$. (...
0
votes
1answer
23 views

Partitioning a set based on binary predicate

Given a collection of objects $X = (x_0,x_1,...,x_{N-1})$ and a binary predicate $F$ which takes as parameters elements of the collection, find a better than $\mathcal{O}(N^2)$ algorithm which ...
2
votes
1answer
65 views

Assume that NP = DTIME(2^sqrt(n)), prove that DTIME(2^sqrt(n)) = DTIME(2^n)

I tried using the padding argument to prove such a thing (as it appeared in Arora's book), but I am not sure how this technique will help me here. I am trying to get to a contradiction to the Time ...
0
votes
1answer
30 views

How does $n^c \lg n, 0<c<1$ compare to other common time complexities

Between what two common time complexities would you place $n^c lg n, 0<c<1$? The following table illustrates the common time complexities. Source: wikipedia

1 2 3 4 5 32