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
1answer
47 views

Time complexity of $a^{n^b}; a,b>1$

What ist the time complexitiy of an algorithm with the running time of $a^{n^b}; a,b>1$? And how is it compared to factorial complexity O(n!)?
0
votes
0answers
46 views

Prove that $T(n)=\omega(n)$?

Edit: can someone provide clear answer with all details Given: $T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$ I was asked to find the minimum value for $a$ for which $T(n)=\omega(n)...
0
votes
1answer
85 views

Explanation of pseudocode and time complexity analysis

I am trying to work my way through some computer science training and I am not able to properly understand the following pseudo code: ...
1
vote
1answer
56 views

If $f(n) = O(g(n))$ then $\log\lfloor f(n) \rfloor = O(\log \lfloor g(n) \rfloor)$?

I need to prove that $\log\lfloor f(n)\rfloor = O(\log\lfloor g(n) \rfloor)$ if $f(n) =O(g(n))$. I know that if $f(n) = O(g(n))$ then $\log f(n) =O(\log g(n))$, but I can't prove the current statement ...
3
votes
0answers
34 views

What's the best non-amortized disjoint set?

In practice, the amortized O(α(n)) data structure is good for every case. But if I want to be pedantic and require each operation to be under a certain time complexity, what's the currently known best ...
1
vote
1answer
25 views

Lower bound for matrix determinant algorithm

I have the an algorithm for computing a matrix determinant: $$\ det(A) = \sum_{i=1}^n (-1)^{i-1} \cdot A_{i1} \cdot det(A_{-i,-1})$$ Where $\ A_{-i,-1} $ is the matrix $\ A $ without the row $\ 1 $ ...
0
votes
0answers
10 views

Complexity of a cutting operation on a list of binary trees

Consider a list of full binary trees of heights $(h_0, h_1, \ldots, h_{n-1})$ where a tree with a single leaf is deemed to have height 0. The list has the property that the height of the tree when ...
0
votes
1answer
24 views

Runtime Analysis: What grows faster?

I was wondering which runtime is a tight upper bound for $f(n,m)= n^2 + 1/2^k$ with $k = n - m$ Intuitively I thought that $f(n,m)$ is in $O(n^2)$ but the longer I am thinking about this the more I ...
0
votes
0answers
23 views

How to explain that a program that runs in NTIME(O(lg n)) is in the class P?

if a non-deterministic program executes only lg(n) decisions on each branch of the computation tree, then the problem this program solves is in P? That means, there is a deterministic algorithm that ...
3
votes
1answer
50 views

Big-O when iterations do not correlate with input

Sorry for the perhaps basic question, but my time at university is long ago and I need to brush up on Big-O stuff for interviews. My question is, what would the time complexity be when an algorithm ...
0
votes
2answers
33 views

Searching for an algorithm with $\Theta(n2^n)$ time complexity

I am searching for an algorithm with a time complexity of $\Theta(n2^n)$ time complexity. I am aware, that e.g. the Fibonacci sequence has a time complexity of $\Theta(2^n)$. My plan was to add a loop ...
0
votes
1answer
25 views

speed of preorder traversal

I want to know the speed of preorder traversal of an tree. I do not mean its order of magntude which we know is O(n). I want something like 27n operations where an operation is precisely defined. ...
3
votes
1answer
51 views

When do you use amortized time complexity and when to use unamortized?

This is my guess: -Use amortized because we want to know the "averaged" complexity over n operations assuming the ...
0
votes
0answers
32 views

String membership in hash set time complexity

Given a string s and a hashset of strings words, what is the time complexity of the operation: ...
5
votes
7answers
2k views

The running time of algorithm is at most $O(n^2)$

The problem is that if an algorithm is $O(n^2)$ then it is also $O(n^3)$ and $O(n^4), O(n^n), \ldots$ and the phrase 'at most' does not make sense in this situation. For this reason, I am not sure ...
3
votes
2answers
99 views

Meaning of 'running time is $O(n^2)$'

I have a question from Introduction to Algorithms by CLRS, When we say "the running time is $O(n^2),$" we mean that there is a function $f(n)$ that is $O(n^2)$ such that for any values of $...
1
vote
1answer
114 views

In Strassen's algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?

In Strassen's algorithm, why does padding the matrices with zeros, in order to multiply matrices that are not powers of 2, not affect the asymptopic complexity? Hi, I was reading this question but I ...
0
votes
1answer
30 views

asymptotic tight bounds for quadratic functions

In Introduction to Algorithms by CLRS, it's said For any quadratic function $f(n)=an^2+bn+c$, where $a$, $b$ and $c$ are constants and $a>0$, $f(n)=\Theta (n^2).$ Formally, to show the same thing, ...
0
votes
1answer
150 views

Time complexity of removing a vertex from a graph represented as collection of adjacency lists

I'm trying to reason about the time complexity of removing a vertex from a graph represented as an adjacency list, which has $n$ vertices and $e$ edges. It is a directed graph, and the list associated ...
0
votes
1answer
42 views

Exact runtime of median of median algorithm

Consider median of median algorithm. If I make to group of size $7$ instead of $5$ then the recurrence equation will be $$T(n)=T(n/7)+T(5/7\cdot n+4)+O(n),$$ which can be proven by induction equal to $...
-1
votes
1answer
36 views

Solution to T(n) = 2T(n/2) + log n

So my recursive equation is T(n) = 2T(n/2) + log n I used the master theorem and I find that a = 2, b =2 and d = 1. which is case 2. So the solution should be O(n^1 log n) which is O(n log n) I looked ...
0
votes
1answer
31 views

Algorithm for assigning items to one of two sets (2-CNF?)

I have a set of items (A, B, C, D, ...) which I want to assign to one of two sets (set1, set2). Trying all possible assignments ...
0
votes
0answers
34 views

Time complexity of a recursive algorithm with two lists as parameters

The goal is to find the function T which describes the time complexity of an algorithm who merges two lists (but the lists are given inversely sorted). The problem is that recursive calls depend on an ...
0
votes
0answers
27 views

Computational complexity of described algorithm

Is algorithm which schedules tasks to machine and then for every time point in the makespan of machine does an operation considered pseudo-polynomial or quasi-polynomial? (if machine execute tasks ...
2
votes
2answers
83 views

Examples of higher order algorithms ($\mathcal{O}(n^4)$ or larger)

In most computer science cirriculums, students only get to see algorithms that run in very lower time complexities. For example these generally are Constant time $\mathcal{O}(1)$: Ex sum of first $n$ ...
0
votes
1answer
69 views

Classification and complexity of generating all possible combinations: P, NP, NP-Complete or NP-Hard

The algorithm needs to generate all possible combinations from a given list (empty set excluded). ...
0
votes
0answers
25 views

Is there a decision problem in NP whose corresponding function problem is not in #P?

I am trying to get an imagination of the class #P for my bachelor thesis. Right now I think of it as a DTM that runs every possible path to run an algorithm on some decision problem at once. But in ...
1
vote
0answers
50 views

Complexity in time and memory for graph search algorithm

I am working on an assignment where I have to write an algorithm to detect all vertices that lie in a cycle in a graph and then calculate its complexity. I have come up with an algorithm in pseudocode....
4
votes
3answers
320 views

Two increasing functions from the set of positive integers to the set of positive integers such that neither f (n) is O(g(n)) nor g(n) is O(f (n))

Here is the question again : Give an example of two increasing functions f (n) and g(n) from the set of positive integers to the set of positive integers such that neither f (n) is O(g(n)) nor g(n) is ...
1
vote
0answers
55 views

Most scalable distributed consensus mechanism based on message complexity?

One of the most challenges in distributed consensus mechanisms is both time complexity and message complexity. For example, PBFT message complexity is O(n^2) that ...
0
votes
0answers
28 views

what is the complexity of the below code? [duplicate]

I wanted to calculate the complexity of this pseudocode. In my knowledge, it is $n^2$ because the last loop only runs 8 times. I wrote a program to test it tends to run 8^logn (approximately). can you ...
2
votes
1answer
417 views

Finding the rectangle with maximum perimeter weight in a 2D array

[Problem Description]: Given an array of size $N \times N$, the task is to find the rectangle with maximum perimeter weight in the array. The perimeter is defined as the number of cells on the sides. ...
1
vote
1answer
37 views

A problem about master theorem and recursion [duplicate]

Prove or disprove the following statement: If $f(n)\in \Omega(n^2)$ and $T(n) = 2T(n/2) + f(n)$ then $T(n) \in O(f(n))$. I think that the statement is false. Do you know any counterexamples?
0
votes
0answers
35 views

The following time complexity is right for the given algorirthm

Calculate the complexity of the algorithm as follows O (n ^ 2) Would it be correct? ...
4
votes
3answers
76 views

What is the difference between saying there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time and $n^{2-o(1)}$ or $\Omega(n^2)$?

I have seen the formulations there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time a problem requires time $n^{2-o(1)}$ a problem requires time $\Omega(n^2)$ being used ...
0
votes
2answers
51 views

Time complexity of ArrayList Insertion : Calculating sum of X + X/2 + X/4 + X/8 + … 1

Here is an excerpt from Cracking Coding Interview book where it's talking about the time complexity of insertion to an ArrayList. I am trying to prove that the sum of $X + \frac{X}{2} + \frac{X}{4} + ...
0
votes
0answers
81 views

Why the time complexity for following pseudocode is O(n^2)?

So, I was going through the Rod-Cutting problem in the Dynamic Programming section of the Introduction to Algorithms by CLRS. Here's the rod-cutting problem statement: Given a rod of length n inches ...
0
votes
0answers
24 views

Counting elements in an array greater than a value and after the value

I have an array composed of integers from 1 through n. For each integer, I want to count the integers which are greater than that integer and occur after the integer's placement in the array in O(n*...
0
votes
1answer
57 views

Comparing the big-$O$ of these four functions

Sometimes you can substitute values for $n_0$ and $c$ in the big-$O$ equation and compare two functions. Or take limits and compare two functions. But for the following functions, for example, taking ...
1
vote
1answer
126 views

Complexity of Radix Sort

I am a little confused by the complexity proof of Radix Sort. For counting sort, the complexity reported is $O(n+R)$, where $n$ is the number of items and $R$ is the range. But this is not entirely ...
1
vote
1answer
41 views

Determing Big Oh Of Given Data

I'm trying to determine the big O time complexity of the following data set where the first column is the input size, and the second column is the execution time in seconds. Where possible, I should ...
0
votes
0answers
65 views

Create a potential function for an abstract queue data structure to show constant amortized-time complexity

Consider a variation of a Queue called MaxQueue, Q, that has the following operations: dequeue(Q): removes and returns the first element of Q enqueue(Q, s): Appends the integer s to the end of Q ...
0
votes
0answers
157 views

Time complexity for computing the highest degree vertex

Consider an undirected and unweighted graph with $n=|V|$ nodes and $m=|E|$ edges stored in adjacency matrix format. What is the time complexity of finding the highest-degree vertex, assuming the ...
1
vote
1answer
29 views

Range sum query - tree representation efficiency

I was reading about possible solutions to the well known problem: Given array A with length N create a structure that enables ...
0
votes
0answers
4 views

Complexity Analysis for complex nested loops [duplicate]

What is the general approach for time complexity analysis when you have a loop structure which is complex? For example if the length of the inner loop is some function o the iteration of the outer ...
2
votes
2answers
55 views

Why do algorithms with runtime of O(n) are said to have asymptotic upper bound, when linear functions don't have asymptotes?

When we have only an asymptotic upper bound, we use $O$-notation. For a given function $g(n)$, we denote by $O(g(n))$ (pronounced “big-oh of $g$ of $n$” or sometimes just “oh of $g$ of $n$”) the set ...
2
votes
1answer
44 views

Is it true that $f(n) = c\cdot g(n) + O(g(n))$ implies $f(n) = O(g(n))$?

Is this true for all $n$ and some $c>0$? I'm thinking the answer is yes, but I'm not sure. My thinking is as follows: $f(n) = c\cdot g(n)$ for all $n$ and some $c>0$ is the definition of Big-Oh. ...
1
vote
0answers
31 views

A genral Turing model with one tape to define sublinear space (L,NL,..)

A genral Turing model with one tape to define sublinear space (L,NL,..) Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and ...
2
votes
3answers
61 views

Determining the number of iterations needed to find the number of bits in an integer

I'm trying to understand the complexity/number of iterations needed to determine the number of bits in an integer. ...
0
votes
1answer
50 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
3 4
5
6 7
40