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

learn more… | top users | synonyms

0
votes
1answer
23 views

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

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 ...
0
votes
0answers
53 views

Running time of an algorithm which is using an array [on hold]

Currently learning how to get running time of an algorithm and slightly confused at my answer (unsure if its right). I have the following: ...
0
votes
4answers
145 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
25 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
67 views

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

The complexity of the below program is given to be O(n!) ...
0
votes
1answer
37 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 ...
-1
votes
0answers
31 views

Big O analysis of algorithm used to check for subtree of binary tree

This is the algorithm I used to check if a Binary tree is a subtree of another Assuming A is the pointer to root of Binary tree P and B is the pointer to the root of Binary tree T. Funtion ...
3
votes
0answers
93 views

Complexity of a naive algorithm for finding the longest Fibonacci substring

Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows: $$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) ...
2
votes
2answers
100 views

Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?

According to page 53 of Modern Computer Arithmetic (pdf), all of the steps in the Schönhage–Strassen Algorithm cost $O(N \cdot lg(N))$ except for the recursion step which ends up costing $O(N\cdot ...
1
vote
1answer
30 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 ...
4
votes
1answer
145 views

Complexity of Hopcroft-Karp

I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where ...
2
votes
1answer
54 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 ...
1
vote
2answers
60 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 ...
2
votes
2answers
75 views

Why do we 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 ...
0
votes
0answers
23 views

Using arithmetic progression sum to show an algorithm is both $\Theta(n^2)$ and $O(n^2)$ [duplicate]

Exercise 4 in http://discrete.gr/complexity/ askes to give an arithmetic progression sum to show that the following algorithm is both $O(n^2)$ and $\Theta(n^2)$. ...
1
vote
2answers
57 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 ...
4
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 ...
0
votes
0answers
30 views

What is the time complexity of Matlab's Hierarchical Clustering?

I'm using mat lab's implementation of hierarchical clustering algorithm, with pdist, linkage , cophenet, dendrogram, and cluster. But I'm not exactly sure where or how to find the time complexity It ...
1
vote
1answer
50 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 ...
1
vote
1answer
100 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
32 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. ...
1
vote
3answers
51 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: ...
1
vote
1answer
40 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 ...
2
votes
0answers
28 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 ...
4
votes
2answers
192 views

Performance impact due to time required for shuffling in Quicksort

As a programmer with non CS background, I am learning algorithms. When explaining the performance of quicksort in an Algorithm book and also elsewhere on the web, I do not see any reference to the ...
0
votes
2answers
56 views

Why don't we calculate swaps and other steps except comparison for finding time complexity of a sorting algorithm? [duplicate]

I was learning some basic sorting techniques with their complexity. However I cannot understand why only the number of comparisons are taken into account while calculating time complexity and ...
0
votes
0answers
16 views

Time complexity of complex nested for loops [duplicate]

What are the time complexities of the following code? I posted this on the general stackexchange website, but it was suggested that I post it here. ...
4
votes
2answers
203 views

Expected number of updates of minimum

I came across the following problem in a exam. We choose a permutation of n elements $[1,n]$ uniformly at random. Now a variable MIN holds the minimum value seen so far at it is defined to $\infty$ ...
1
vote
0answers
25 views

Complexity of a nested for loop [duplicate]

I'm trying to work through various exercises in Skiena's "Algorithm Design Manual." One problem that I am stuck on is as follows: What value is returned by the following function? Express your ...
2
votes
1answer
46 views

Analysis of Algorithms: Applying Concepts [duplicate]

I believe I understand the concepts of algorithm analysis. However, I'm not fully confident in applying those concepts. I'd appreciate help in bridging the gap between concept and application. I ...
0
votes
1answer
117 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 ...
0
votes
3answers
133 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
116 views

Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$?

I am reading Prim's MST for the first time and wanted to implement the fast version of it . $m$ - The number of edges in the graph $n$ - The number of vertices in the graph Here's the algorithm ...
1
vote
1answer
116 views

Recurrence of T(n) = T(n/3) + T(2n/3) [duplicate]

I've searched online for this but I only seem to find answers for a similar equation: T(n) = T(n/3) + T(2n/3) + cn But the one I'm trying to solve is: ...
-1
votes
1answer
42 views

What's the time complexity of this append method? [closed]

I made a method that appends a sequence to another sequence. So: (append [1,2,3] [4,5,6]) = [1,2,3,4,5,6] CODE In C# ...
0
votes
1answer
28 views

The number of executions of the count statement; how many?

How many times does the statement count in line 5 executes in terms of $n$? ...
5
votes
3answers
136 views

Are there dynamic programming examples that run in exponential time?

Are there dynamic programming examples that run in exponential time? Every example that I've seen so far constructs the top half of a matrix in a bottom-up fashion ($n^2$) from the base case and ...
2
votes
7answers
650 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 ...
-1
votes
2answers
122 views

How to find the cost of pseudocode with a nested loop and a nested if statement?

How can I find the cost of pseudocode with a nested loop and a nested if statement? On the left hand side is an example from a textbook I am following. On the right hand side is pseudo code that I ...
2
votes
1answer
87 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 ...
1
vote
1answer
66 views
4
votes
1answer
107 views

Which computational model is used to analyse the runtime of matrix multiplication algorithms?

Although I have already learned something about the asymptotic runtimes of matrix multiplication algorithms (Strassen's algorithm and similar things), I have never found any explicit and satisfactory ...
3
votes
1answer
61 views

Compare asymptotic WC runtime with measured AC runtime

I have an algorithm and I determined the asymptotic worst-case runtime, represented by Landau notation. Let's say $T(n) = O(n^2)$; this is measured in number of operations. But this is the worst ...
1
vote
1answer
264 views
1
vote
1answer
59 views

Runtime analysis of a “find the secret number” algorithm

The algorithm task is to find an integer (range is not known). the function guess(num) returns one of three chars: '>','<' or '='. Find the secret number ...
1
vote
0answers
98 views

FInd the running time complexity of functions [closed]

For each of the procedures below, let $T(n)$ be the running time. Find the order of $T(n)$ (i.e., find $f(n)$ such that $T(n) ∈ Θ(f(n))$. Do not worry about how rounding errors affect running time. ...
1
vote
1answer
27 views

Understanding expected time bound for unsuccessful search in R-way tries

As per Tries slides (page 17) from Algorithm 4th edition book by Robert Sedgewick, the asymptotic expected runtime for an unsuccessful search in $R$-way tries miss is $O(\log_R N)$. Can someone please ...
1
vote
1answer
390 views

Complexity analysis of while loop with two conditions

I am curious how to do a line by line analysis of this piece of code using the "Big O" notation. ...
0
votes
1answer
151 views

How to find the asymptotic runtime of these nested loops? [duplicate]

i=n; while(i>0) { k=1; for(j=1;j<=n:j+=k) k++; i=i/2; } The while loop has the complexity of $\lg(n)$ the j value of inner loop runs ...
5
votes
1answer
146 views

Largest set of vertices that is larger than its set of neighbors

I am reading a unpublished paper describing an algorithm. In one step of the algorithm, there is a bipartite graph $G(X,Y,E)$, where $X=\{1,...,n\}$. For every subset $X' \subseteq X$, they define ...