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
15 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
1answer
34 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)&...
-3
votes
0answers
25 views

Monotonically increasing function such that f(n) is not O(g(n)) and g(n) is not O(f(n))

Give an example of the monotonically increasing function such that f(n) is not O(g(n)) and g(n) is not O(f(n)). Also give some tip how to find the function like that.
0
votes
0answers
20 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
76 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
166 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
15 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
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 ...
2
votes
2answers
43 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
52 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
93 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
300 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 ...
-6
votes
0answers
27 views

Time Complexity of multiple functions calling each other [closed]

Time Complexity of multiple functions calling each other
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
66 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
78 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
67 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
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 ...
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
34 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
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
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
25 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
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 ...
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
56 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
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?
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 ...
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.
0
votes
0answers
13 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
37 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
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 \...
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
64 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 ...
-2
votes
1answer
51 views

Time complexity of similar-looking functions

What is the time complexity of the following functions, and why? ...
0
votes
1answer
38 views

Which of these two functions has a higher order of growth/complexity?

Consider the following functions: $$f(n)=2^{\log^*n} \text{ and } g(n)=\sqrt{2}^{\log{n}}$$ Using $\log{}$ properties I think that $g(n) < f(n)$, since: $f(n)\sim n$, $g(n)\sim n^{\frac{1}{2}}$, ...
14
votes
1answer
3k views

Hardness of a problem which is the sum of two NP-Hard problems

Consider the problem of computing an exponential sum over a certain function $g(x)=f(x)+h(x)$, that is computing $$\sum_{x}g(x)=\sum_{x}f(x)+\sum_{x}h(x)$$ now if we know that $\sum_{x}f(x)$ and $\...
2
votes
0answers
57 views

P/NP - Proof that SAT-TM is NP-complete uses certificate

To prove that SAT-TM (Turing machine emulating the satisfiability problem) is NP-Hard $$\text{SAT-TM}:=\{⟨M,p,1^k⟩ \; | \;∃c,\; |c|\leq p(k), \;\text{such that M accepts c in ≤k steps}\}$$ my ...
1
vote
2answers
29 views

Given a list of vertices in a binary tree output minimal sublist with the same lowest common ancestor

The input: a binary tree and a list $L$ of vertices in that tree. The output: a sublist of $L$ of minimal length that has the same lowest common ancestor as $L$. If there is several sublists of ...
1
vote
1answer
42 views

Counting letter frequency in array in O(1) with hash function

I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p'] There are several ways to do this: A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ ...
0
votes
1answer
37 views

Finding the Big-O and Big-Omega bounds of a program

I am asked to select the bounding Big-O and Big-Omega functions of the following program: ...
4
votes
2answers
45 views

Finding which functions are bounded by $O(n^2)$

I am asked to select the functions that are bounded by the Big-Oh function O(n^2): $f(n) \in O(n^2)$. $f(n) = \sum_{i=1}^{n} n$ $f(n) = \sum_{i=1}^{n} i$ $f(n) = n + n^2$ $f(n) = 1$ I choose the ...
0
votes
1answer
15 views

Relaxation possibilities of the lower bound worst case sorting algorithms without quantum computation

The sorting algorithms (merge-sort, quicksort...) are tought to have an absolutely hard lower bound which can not be outperformed by computation alone and this bound is $n*log_{2}(n)$, The reason for ...
1
vote
1answer
19 views

Why is the Kth Largest Element solution using a MinHeap O(N lgK) in complexity?

This is a rather well known solution to the $k$-th order statistic problem which requires us to find the $k$-th largest number in an unsorted array with $n$ elements where $1 \leq k \leq n$: ...
0
votes
1answer
29 views

How to analyse the worst-case time complexity of this algorithm(a mix of Bubble Sort and Merge Sort)?

Suppose I have a sorting algorithm that sorts a list integers. When the input size(the number of elements) $n$ is odd, it sorts using Bubble Sort and for even $n$ it uses Merge Sort. How do we perform ...
1
vote
1answer
42 views

Asymptotic growth of a series

How we can prove that: $$ \sum_{k=1}^{c \log n-1}\:k\cdot \left(\frac{1}{2}\right)^{\frac{k}{3}}\in O\left(1\right) \quad \mbox{?} $$

1
2 3 4 5
38