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
0
votes
1answer
97 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 ...
1
vote
1answer
3k 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 ...
3
votes
1answer
1k 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: http://en.wikipedia....
2
votes
2answers
184 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
1k 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, ...
3
votes
2answers
75 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 ...
1
vote
1answer
361 views

Confusion regarding several time complexities including the logarithm

I am new to Advanced Algorithms and I have studied various samples on Google and StackExchange. What I understand is: We use $O(\log n)$ complexity when there is division of any $n$ number on each ...
3
votes
1answer
678 views

Randomized Median Element Algorithm in Mitzenmacher and Upfal: O(n) sorting step?

In the last section of chapter 3 (page 54) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the ...
-1
votes
1answer
211 views

Time Complexity of Algorithm

I need help with finding out the time complexity of the following algorithm: ...
1
vote
1answer
162 views

Runtime of various versions of binary search

I was given the following code and was told to find the best and worst case running times in big theta notation. (Below is in python) ...
3
votes
1answer
9k views

Time Complexity for Creating a Graph from a File

Assume that I have a file that consists of pairs of numbers separated by a space. These numbers are the labels for vertices in my graph. For example: ...
1
vote
2answers
223 views

Measuring time complexity of algorithm

I was going through a past paper question but I don't have any answers to know if I'm working out the problems correctly or not. I need to find the time complexity for: ...
2
votes
1answer
424 views

Finding asymptotically tight bounds $\Theta$ of two procedures

I would like to check time complexity of two procedures for which I am not totally convinced that I got it right. Now the first procedure is this: ...
1
vote
1answer
2k views

Time complexity of a triple nested for loop for ThreeSum problem [duplicate]

I am new to Algorithms and am currently confused about the running time of the ThreeSum program. If we look at ThreeSum's count function: ...
7
votes
2answers
635 views

How can you shuffle in $O(n)$ time if you need $\Omega(n \log n)$ random bits?

A shuffling algorithm is supposed to generate a random permutation of a given finite set. So, for a set of size $n$, a shuffling algorithm should return any of the $n!$ permutations of the set ...
1
vote
1answer
550 views

Closed-form Expression of the Expected value of the Cost of D&C Algorithm?

Let there is a binary-string, $B$, of length $N$. The probability of occurrence of 0 and 1 in this binary-word is $p$ and $q$ , respectively. Each bit in the string is independent of any other bit. ...
3
votes
1answer
850 views

Theta Runtime of Nested for Loops

I have two for loops, one nested within the other. I have two int variables n and U, where U > n. I know that the outer loop runs exactly U times (pretty much <...
4
votes
1answer
694 views

Complexity of the V-opt heuristic Traveling Salesman algorithm

The paragraph on V-opt heuristic TSP algorithms at this site mentions a very effective algorithm due to Lin-Kernigham-Johnson. That page says: For many years Lin–Kernighan–Johnson had identified ...
0
votes
2answers
3k views

Average Time Complexity of Two Nested Loops

Recently I have had this question in one of my interviews. You have 1 Million sorted integer, you have a value of $x$, compare each pair in this array and if the addition of two pair is less or equal ...
3
votes
3answers
6k views

Runtime of searching for a number in an array?

Searching for a number in an array is said to have a runtime of O(n) because there may be cases where the number doesn't exist in the array. In such cases, you'd have to have gone through the entire ...
4
votes
2answers
696 views

Analysis of algorithms, 'big O' question

The main question is, how exactly is the big O analysis calculated on routines? Is there a specific formula that relates what each function in a program does to a big O calculation? Also, what about ...
8
votes
2answers
932 views

What constitutes one unit of time in runtime analysis?

When calculating runtime dependence on the input, what calculations are considered? For instance, I think I learned that array indexing as well as assignment statements don't get counted, why is that?
5
votes
1answer
334 views

Why don't we emphasize “length of input string” when considering time complexity of sorting algorithms?

The knapsack problem is $O(c\,n)$ where $c$ is the capacity of knapsack and $n$ is the number of items. Yet it's exponential because the size of the input is $\log(c)$. However, why don't we ...
2
votes
1answer
88 views

Complexity of a particular algorithm

I am a bit confused about calculating complexities. Above is a C++ program converting a char array into an int, incrementing the value, parsing it back to char array. ...
4
votes
1answer
218 views

Doubt with a problem of grown functions and recursion tree

I'm confused to conclude the recursion tree method a guess for the next recurrence: $$T(n)=3T\left (\left\lfloor \frac{n}{2}\right \rfloor\right) +n$$ I write some costs for the levels of tree, you ...
2
votes
2answers
216 views

Complexity of an algorithm for bounding a region in 2D

First I apologize if the title is unclear, but I didn't find anything better. I'm solving a differential equation that has two parameters , here denoted by points of a plane.These parameters are real ...
7
votes
3answers
5k views

Complexity of finding the largest $m$ numbers in an array of size $n$

What follows is my algorithm for doing this in what I believe to be $O(n)$ time, and my proof for that. My professor disagrees that it runs in $O(n)$ and instead thinks that it runs in $\Omega(n^2)$ ...
1
vote
1answer
207 views

Finding the lower bounds of an algorithm

I am struggling to calculate the lower bounds of an algorithm. What is the right way to proceed. For eg, I have the following algorithm ...
2
votes
2answers
129 views

Why don't we scale the cost of memory access when analyzing runtime of algorithms?

Runtime for many programming languages is typically analyzed either assuming each operation takes a constant amount of time, or assuming each operation takes a logarithmic amount of time in the size ...
8
votes
0answers
563 views

Predecessor query where the insertion order is known

Assume I want to insert elements $1$ to $n$ into a data structure exactly once, and perform predecessor queries while inserting these elements (so insert(x) and <...
1
vote
1answer
107 views

Resolving this recurrence equation [duplicate]

I have this recurrence equation: $T(n) = T(n/4) + T(3n/4) + \mathcal{O}(n)$ $T(1) = 1$ I know that the result is $\mathcal{O}(n \log n)$ but i don't know how to proceed.
3
votes
2answers
1k views

Finding no. of leaf nodes for each node in a BST

A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is $\qquad \min(\#\text{...
1
vote
1answer
87 views

Approximate time for selection operation using index when equality is on nonkey

In database query processing, the approximate time for selection operation using primary index when equality is on key is $2(b_s + b_t)$ where $b_s$ is disk seek time and $b_t$ is disk transfer time (...
5
votes
1answer
917 views

Parallel merge sort using hypercube connection template

I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear. What I ...
2
votes
1answer
1k views

Decreasing runs of inner loop in outer loop [duplicate]

I am trying to determine the worst case runtime of this program: while n > 1 for i = 1,..,n m = log(n) n = n/2 Obviously the outer loop runs ...
2
votes
1answer
287 views

How to get expected running time of hash table? [duplicate]

If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in ...
4
votes
1answer
10k views

Triple nested for-loops [duplicate]

Possible Duplicate: A puzzle related to nested loops I am trying to count the exact/total number of iterations the following nested for-loops are executed: ...
-2
votes
1answer
307 views

Complexity of slightly tricky for loop

I'm trying to determine the complexity of this for loop: for (int j =3; j <= n-2; j+=2) { .... } By trying out lots of examples, I came up with $\frac{n-4}{...
-2
votes
1answer
6k views

Complexity of a while loop that divides by parameter by three each iteration

I've learned that a while loop such as int i = 100; while (i >= 1){ ... ///Stuff i = i/2 } will run in logarithmic time, specifically, ...
2
votes
2answers
424 views

Common Algorithms without Asymptotically Tight Bounds

I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds, but are there actually common algorithms in computer science that don't have asymptotically tight bounds ...
4
votes
1answer
141 views

How to get the expected running time of an algorithm

I have an algorithm which, basically given an array of $n$ numbers, checks if there is any repeated numbers in the array, and returns true if there is and false otherwise. It uses a direct access ...
4
votes
4answers
7k views

Why does a recurrence of $T(n - 1) + T(n - 2)$ yield something in $\Omega(2^{\frac{n}{2}})$?

I am trying to analyze the running time of a bad implementation of generating the $n$th member of the fibonacci sequence (which requires generating the previous 2 values from the bottom up). Why does ...
3
votes
1answer
5k views

Worst case analysis of bucket sort using insertion sort for the buckets

Suppose I am using the Bucket-Sort algorithm, and on each bucket/list I sort with insertion sort (replace nextSort with insertion sort in the wikipedia pseudocode). In the worst case, this would ...
4
votes
2answers
1k views

Analyzing programs with multiple for-loops

If they were all linked to make a condition such as ($1 < i < j < k < n$), I know how to solve, but the last loop is disconnected so I have no clue on how to do these... the ones like <...
2
votes
2answers
1k views

Finding the complexity of a recursive method

An assignment question asks me to find the complexity of a [tail] recursive algorithm, copied below. While I understand all the complexity specifics, for example that the while loop's complexity is $n-...
4
votes
1answer
5k views

What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap?

Problem: Consider a graph $G = (V, E)$ on $n$ vertices and $m > n$ edges, $u$ and $v$ are two vertices of $G$. What is the asymptotic complexity to calculate the shortest path from $u$ to $v$ ...
5
votes
3answers
1k views
2
votes
1answer
3k views

Question about Prims algorithm where weights are between 1 and some constant W

I came across a couple of solutions to one of the problems that is in the CLRS textbook (pg. 637 23.2-5 edition 3). I am wondering if anyone can make a clarification as to the stated running time of ...
10
votes
1answer
6k views

Potential function binary heap extract max O(1)

I need help figuring the potential function for a max heap so that extract max is completed in $O(1)$ amortised time. I should add that I do not have a good understanding of the potential method. I ...
1
vote
1answer
3k views

Computing the clustering coefficient

I saw in this video that computing clustering coefficient of central node of a star graph using the following algorithm is $\Theta(n^2)$ and for a clique it is $\Theta(n^3)$. is that correct? ...