Questions tagged [runtime-analysis]

Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.

Filter by
Sorted by
Tagged with
6
votes
1answer
411 views

Runtime of Euclidean Algorithm

Given two $n$-bits numbers $a$ and $b$, I am not sure on how to find the runtime of the euclidean algorithm for finding the $\gcd$ of $a,b$. The problem (for me) in here is that apart from the size of ...
2
votes
1answer
2k views

Amortize time for a counter with the operations INCREMENT and DECREMENT

Let a binary counter with the operations INCREMENT and DECREMENT. I need to show that you can't implement this kind of counter with constant amortized time per operation. Hence, I need to show ...
2
votes
2answers
271 views

Why do compute time complexity for algorithms? [closed]

I read about Big-O notation with modular arithmetic. So, Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation ...
1
vote
0answers
42 views

Runtime of “Look and Say” [duplicate]

I am trying to figure out what the time complexity is for a "Look and Say" sequence generator which receives an integer n and outputs the nth term in the look and say sequence. I'm looking at the ...
3
votes
1answer
240 views

Which algorithms have runtime recurrences like $T(n) = \sqrt{n}\,T(\sqrt{n}) + O(n)$?

The algorithms using the "divide and conquer" (wiki) design strategy often have the time complexity of the form $T(n) = aT(n/b) + f(n)$, where $n$ is the problem size. Classic examples are binary ...
1
vote
1answer
2k views

Hamming Weight to find the sum of 1 bits in the range between A and B inclusive [closed]

I am trying to find the sum of 1 bits in the range between A and B inclusive, where -2^31 <= A <= B <= 2^31 - 1 Input Format: The first line contains the number of test cases T (<=1000)...
2
votes
1answer
52 views

Expressing pseudo-polynomial runtime solely in terms of the input size

In case we have an algorithm which is pseudo-polynomial and runs in $O(n^2C)$ for some $C$ that is encoded in binary. Is it correct to say that if $C=2^n$ then $O(n^2C)=O(n^22^n)$ and because $n=\...
2
votes
1answer
291 views

Asymptotic runtime for querying an interval tree

Suppose that we have an array of size n and we want to build an interval tree for all possible ranges that can be created inside this array. So in our leafs we have ...
-1
votes
1answer
2k views

Runtime of nested loops

What is the asymptotic runtime of fthe ollowing piece of code in terms of number of updates to S in worst case. ...
15
votes
3answers
5k views

Brzozowski's algorithm for DFA minimization

Brzozowski's DFA minimization algorithm builds a minimal DFA for DFA $G$ by: reversing all the edges in $G$, making the initial state an accept state, and the accept states initial, to get an NFA $N&#...
0
votes
0answers
400 views

What is the average runtime of appending items to arrays?

It is the time of the year again in colleges for final exams and I am preparing mine as of now and I am finding myself in hot water when it comes to understanding the running times of appending items ...
1
vote
2answers
145 views

Calculating the runtime for a recursive algorithm [duplicate]

If the runtime of a recursive algorithm could be expressed as $T(n) = \begin{cases}O(1) & n \leq c \\ k * T\left(\frac{n}{k}\right) + \left(k + n * k \right)\end{cases}$ what would be the ...
1
vote
1answer
251 views

Average Case runtime for random choice search

Assuming we have an array with $n$ Elements and want to find an unique element by randomly (uniformly) choosing. What would be the average case runtime? My thoughts so far: The chance to find the ...
0
votes
1answer
420 views

Big O Notation Explained [duplicate]

Our teacher gave us the following definition of Big O notation: O(f(n)): A function g(n) is in O(f(n)) (“big O of f(n)”) if there exist constants c > 0 and N such that |g(n)| ≤ c |f(n)| for all n > N....
1
vote
1answer
160 views

Sorting with a recursive oracle

It is known that the runtime complexity of sorting is $\Theta (n \log n)$. But what if we have, for every input array of size $n$, an oracle that can sort any array of $k<n$ numbers in constant ...
9
votes
1answer
1k views

Solving recurrence relation with two recursive calls

I'm studying the worst case runtime of quicksort under the condition that it will never do a very unbalanced partition for varying definitions of very. In order to do this I ask myself the question ...
1
vote
2answers
176 views

Finding recursion for runtime of code [duplicate]

This is the first time we have to do recursive/closed form expressions WITH code in class and I really have no idea how to approach this. My course notes that the prof put up don't really help as he ...
1
vote
1answer
421 views

Data structure for range-value-sum

I have to be able to perform insert, delete, range-value-sum, and range-2-max-values with a data structure. Range-value-sum(xl,xr): with a range [xl,xr] (for a range query), it reports the sum of ...
1
vote
1answer
279 views

What is the runtime of Mergesort if we switch to Insertion Sort at logarithmic depth?

Consider the Mergesort algorithm on inputs of size $n = 2^k$. Normally, this algorithm would have a recursion depth of $k$. Suppose that we modify the algorithm so that after $k/2$ levels of recursion,...
0
votes
0answers
910 views

Partial Sum operation & solution - Optimizing to O(logn)

I approached this problem where I have to write an add(key, value), insert(key, value), delete(key,value) and partial_sum(value) which reports the sum of all the elements in the structure that are ...
0
votes
0answers
18 views

Big o notation for the algo [duplicate]

Asked this at programmers Stack Exchange, was recommend to ask here : What would be the big o for the algo: for (i=0; i < n*n; i++) for(j=0; j<i*i; j++) ...
6
votes
1answer
4k views

What is the intuition behind the Potential Function in Amortized Analysis of some algorithm?

I have come across many amortized analysis using a potential function. They all look magical to me. Everything works perfectly but I never got the intuition behind how they come up with such a "...
0
votes
1answer
662 views

What is the runtime of the following code? [duplicate]

Can you explain to me how you get the Big O notation for the runtime of the following snippet of code? ...
1
vote
0answers
350 views

Influence of edge number and priority-queue implementation on the runtime of Dijkstra

When we try to find the shortest path of a directed weighted graph using Dijkstra’s algorithm, is there a relation between the number of edges/vertices of the graph and the different implementations ...
7
votes
1answer
20k views

Recurrence for recursive insertion sort

I tried this problem from CLRS (Page 39, 2.3-4) We can express insertion sort as a recursive procedure as follows. In order to sort A[1... n], we recursively ...
2
votes
1answer
372 views

Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?

According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved ...
-1
votes
1answer
190 views

Quick Sort Algorithm When Partition is Constant Time

I ran into a question about Quick Sort Algorithm. Suppose in Quick Sort, Partition procedure take C times, (need constant time). if we use random data as input, what is the order (time complexity) of ...
1
vote
0answers
25 views

How to conduct time complexity analysis for an implemented algorithm [duplicate]

Main task In my bachelor degree's thesis I've developed an algorithm for recommender systems which uses personalized PageRank with some particular features as nodes. In the recommender systems' field,...
19
votes
3answers
2k views

Why use comparisons instead of runtime for comparing two algorithms?

I notice that in a few CS research papers, to compare the efficiency of two algorithms, the total number of key comparison in the algorithms is used rather than the real computing times themselves. ...
0
votes
4answers
3k views

Proving Quicksort has a worst case of O(n²)

I am sorting the following list of numbers which is in descending order. I am using QuickSort to sort and it is known that the worst case running time of QuickSort is $O(n^2)$ ...
0
votes
1answer
3k views

tightest upper bound on binary search tree insertion? [closed]

The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced What will be the tighter upper bound on this,will it become O(logn) I have read that ...
3
votes
1answer
5k views

Inserting vertex in an adjacency matrix

If a graph with $v$ vertices is represented in the form of adjacency matrix . Then, adding a new vertex to the existing graph requires how much time ? Is it $O(v^2)$ or $O(2v)$ . We have the ...
-1
votes
1answer
123 views

How the below program is taking O(n!) time? [closed]

The complexity of the below program is given to be O(n!) ...
0
votes
1answer
127 views

Connection of “modern” runtimes and number of steps on a Turing machine

Why an evaluation of Turing machine efficiency is equal to the algorithm which is implemented by this machine and vise versa? For example, we can say that efficiency of merge sorting algorithm is O(...
1
vote
1answer
133 views

Runtime analysis of sorting an array with known number of inversions

I'm having difficulties with analyzing the worst-case runtime of this following case: I'm given an array that has $n$ natural numbers. Out of all $\binom{n}{2} = \frac{n(n-1)}{2}$ possible pairs ...
2
votes
1answer
819 views

Time complexity of proximity search in distance matrix

I am a high school student computationally studying the 3-dimensional structure of chromosomes by 40 kilobase loci. In a nutshell, loci that are close in space tend to express their genes at the same ...
5
votes
2answers
1k views

How fast can we identifiy almost-duplicates in a list of strings?

I'm having trouble figuring out the upper bound running time for this scenario: Input: $N$ number of strings $M$ upper bound of string length $T$ threshold for edit distance (2 strings with a ...
3
votes
1answer
563 views

What is the complexity of depth first traversal that don't label nodes as discovered?

I've found an algorithm that acts like a depth first traversal that don't recognizes nodes that have been visited before. A / \ B C \ / D | E If run ...
2
votes
2answers
2k views

Time cost of thread creation

While creating an algorithm, the following question came up: In uniform cost, what is the time cost of a process that creates a thread? Is there a difference between creating a thread in a thread ...
3
votes
7answers
4k views

Checking if there are 2 elements in an array that sum to X in O(n lg n)

I have thought about the most useful way of checking an array for 2 elements that sum to X. The trivial solution is to check the sum of every element with every element, and the complexity of this ...
3
votes
1answer
584 views

Number of iterations of the Euclidean algorithm

I have a doubt about the runtime of the Euclidean algorithm; the slide of my Professor says: The calculation of $\mathrm{GCD} (a, b)$ stops at the most after $2\log_2 a$ iterations. Since $...
2
votes
1answer
1k views

Leftist heap - determining time complexity

The time complexity of merge (union) operation is said to be $O(\lg (n_1 + n_2))$, where $n_1$ and $n_2$ are the numbers of elements in the merged heaps, respectively. I do not understand this - the ...
0
votes
3answers
795 views

Calculating time complexity of two interdependent nested for loops

Consider the following code segment : for (int i = 1; i <= n; i++ ) { for (int j = 1; j <= n; j = j + i ) { printf("Hi"); } } Here, the ...
0
votes
1answer
722 views

Why is there a 2n+1 comparison for a linear search algorithm?

Suppose an algorithm goes through a list of n integers and for every iteration of the loop it is needs to check if the current evaluated element of the list is even. If it is even, return the index of ...
5
votes
5answers
2k views

Optimal Algorithm for checking if a number is a multiple of three

I'm just starting a course on Computational Number Theory and have very little Computer Science background but definitely know enough about the big-O notation. I currently have an assignment to work ...
2
votes
1answer
339 views

Big O running time for this algorithm?

Here's the code for the algorithm: Foo(n) lcm = 1 for i = 2 to n lcm = lcm*i/Euclid(lcm,i) return lcm The running time of ...
1
vote
1answer
116 views

Time Complexity of Halley's Method

What is the time complexity of Halley's Method? I am thinking ${\cal O}(\log(n)F(n))$, or something very similar to Newton-Raphson, but I feel as though there should be some change to the complexity ...
1
vote
1answer
98 views

Lower bound on number of comparisons needed to search for a number in a sorted 3-d array

Suppose we have an $N \times N \times N$ 3-d sorted array meaning that every row,column, and file is in sorted order. Searching for an element in this structure can be done using $O(N^2)$ comparisons. ...
2
votes
3answers
68 views

Confusion with the Running Time of an algorithm that finds duplicate character

I have the following simple algorithm to find duplicate characters in a string: ...
2
votes
0answers
63 views

Lower-bounds of running-time for output sensitive Algorithms

Let me ask my general question using a specific example, namely range searching: Given a set of points in the plane and an axis parallel rectangle, report all points lying in the rectangle. If the ...