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

learn more… | top users | synonyms

0
votes
0answers
17 views

Radix Tries, Tries and Ternary Search Tries

I originally posted this over on Stackoverflow but realised that it may be better suited to the Computer Science zone. I'm currently trying to get my head around the variations of Trie and was ...
1
vote
1answer
76 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
22 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
45 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
25 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
26 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
162 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
42 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
15 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
187 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
23 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
29 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
62 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
2answers
75 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
78 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
59 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
36 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
19 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$? ...
4
votes
3answers
97 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 ...
-1
votes
2answers
75 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
49 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
56 views
4
votes
1answer
92 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
53 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
181 views

Bubble sort complexity

So I have this code: ...
1
vote
1answer
53 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
68 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
19 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
195 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
133 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
126 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 ...
3
votes
1answer
87 views

Relation between space and time complexity for machines with write once read many (WORM) memory

While thinking about different calculi for predicate logic (like natural deduction and sequent calculus), I noticed that these calculi are (often) presented in a form suitable for "human computers". A ...
1
vote
3answers
138 views

Worst run-time for 3 nested loop

Suppose we need to find a tight asymptotic bound on the worst case run time of the following program ...
0
votes
1answer
81 views

What is the complexity of this bubble sort algorithm? [duplicate]

I have been doing a little reading up on bubble sort and have read on wikipedia that it's complexity is measured as $\Theta(n^2)$ This bubble sort however is slightly more efficient. I thought this ...
4
votes
4answers
222 views

When does an algorithm run in $O(1)$ time?

When can an algorithm be said to have $O(1)$ complexity? My doubt is if $n$ is specified to be a large number but constant and we cannot implement it in reality without a loop even then can we call it ...
1
vote
1answer
2k views

Best and worse case inputs for heap sort and quick sort?

So given a input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts? ...
-1
votes
2answers
79 views

Recurrence for total number of extraneous key insertions in a hash table

I have a practice exam question that I don't know how to set up a recurrence for. It is dealing with a hash table. The question is as follows: Suppose that a hashing strategy is designed so that ...
1
vote
1answer
157 views

Sum number of times statement is executed in triple nested loop

I have this code fragment: for( i=0; i<n; i++ ) for( j=0; j<i; j++ ) for( k=0; k<j; k++ ) S; I need to find the number of times ...
0
votes
1answer
38 views

experimental analysis of running times in extendable table [closed]

I was given the following homework question: Implement an extendable table using arrays that can increase in size as elements are added. Perform an experimental analysis of each of the running ...
0
votes
1answer
661 views

How to analyze/test a binary search algorithm?

I was asked to "Compute the average runtime for a binary search, ordered array, and the key is in the array." I'm not quite sure how to approach this problem. Isn't the runtime of binary search O(log ...
-1
votes
1answer
61 views

Time complexity of an algorithm [closed]

Currently stuck on a question. "Assume the time complexity of an algorithm on input size is 6n^3. If the algorithm takes 10 seconds to execute for an input size of n. Then how many seconds will it ...
2
votes
1answer
190 views

Given an array of N integers, how can you find M elements to remove so that the array will end up in sorted order?

Here is my approach First I compute the longest non decreasing sub-sequence in $N \log N$ time. Algorithm to do this (that only uses arrays and binary search) can be found here: ...
3
votes
3answers
254 views

What is the asymptotic runtime of this nested loop? [duplicate]

I am trying to analyse the runtime of this algorithm: for(i=1; i < n; i++){ for(j=1; j <= i; j++){ statement1; } } Expanding the ...
2
votes
2answers
93 views

Deriving the exact number of execution times

So I'm studying for my data structures midterm and my professor gave out a sample midterm with the answers, but I'm having a hard time understanding one of the questions. Here's a screen cap: The ...
4
votes
1answer
369 views

Recursive equation for complexity: T(n) = log(n) * T(log(n)) + n

For analyzing the running time of an algorithm , I'm stuck with this recursive equation : $$ T(n) = \log(n) \cdot T(\log n) + n $$ Obviously this can't be handled with the use of the Master Theorem, ...
5
votes
2answers
233 views

Complexity of keeping track of $K$ smallest integers in a stream

I need to analyze the time complexity of an online algorithm to keep track of minimum $K$ numbers from a stream of $R$ numbers. The algorithm is Suppose the $i$th number in the stream is $S_i$. ...
2
votes
1answer
86 views

Big O and program calls with varied input sizes

Suppose I have a program p that has time complexity $O(n)$ and a second program q that calls program p $m$ times. If we know the input size of p will be the same every one of those times (n), we can ...
2
votes
2answers
61 views

How to include calls to an $O(n)$ subroutine on finite-sized inputs in an analysis?

I am trying to calculate the runtime complexity of a function that does not have fixed size input, but uses several helper methods that do have fixed size input. I was unsure of how to include the ...
12
votes
0answers
203 views

Do functions with slower growth than inverse Ackermann appear in runtime bounds?

Some complicated algorithms (union-find) have the nearly-constant inverse Ackermann function that appears in the asymptotic time complexity, and are worst-case time optimal if the nearly constant ...