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

learn more… | top users | synonyms

-3
votes
0answers
12 views

worst case runtime in big o [duplicate]

Can someone help me find the worst case runtime of the following in big o notation please? ...
-3
votes
0answers
17 views

Worst case big o runtime [duplicate]

Hello can someone help me find the worst case big o runtime of the following algorithm in terms of n? ...
0
votes
0answers
14 views

Count comparisons in insertion sort that uses binary search to find correct postion

Assume a list $L$ is to be sorted using the following variation of insertion sort: For $2 \le i \le n$, to insert key $L[i]$ do a binary search on the list $L[1..i-1]$ to find the correct position. ...
-3
votes
0answers
22 views

Question about big-O notation (specific example) [duplicate]

i have a question about big-O notation. I Really appreciate if anyone help me out, because this is driving me crazy!! here is the Algorithm : ...
-1
votes
0answers
35 views

How to calculate the time complexity of the following function [duplicate]

The time complexity of the following code is O(2^n), could you please explain to me why? int f(int n) { if (n == 1) return 1; return 1 + f(f(n-1)); } Thanks ...
0
votes
1answer
38 views

Average Time Complexity of Searching An Array [closed]

Why is the average time complexity of searching an array $O(n)$? Is it because if the element does not exist, then $n$ searches must be done. If the element is at the end of the array then $n$ must ...
1
vote
1answer
34 views

Verifying a solution vs. finding one

There is an algorithmic problem $A(n)$, where $n$ is the size of the problem. It is known that, for every candidate solution S, the time it takes to verify whether it is a correct solution to $A(n)$ ...
1
vote
0answers
35 views

Given an algorithm, what are the probabilities for its run-time cases?

I am given this algorithm And I am also given the fact that $1 \leq k \leq n$. If we let X be the number of times line 2 is executed, then I am supposed to find the run-time probabilities for the ...
1
vote
1answer
32 views

How to write recurrence relation for the following scenario?

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 min{no. of leaf-nodes in ...
-1
votes
0answers
15 views

Shouldn't the outer sigma run from 0 to N-2 for selection sort runtime?

This is code from https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-25/19-sorting2-select-insert-shell.pdf slide 6 ...
0
votes
1answer
60 views

What is “potential speedup” in parallel computing?

There is an example problem from p506 of Computer Organization and Design, Fifth Edition: The Hardware/Software interface by David A. Patterson, John L. Hennessy I wonder how "potential speedup" ...
0
votes
1answer
30 views

Time Complexity proof for Segment Tree implementation of the ranged sum problem

I understand that segment trees can be used to find the sum of sub array of $A$. And that this can done in $\mathcal{O}(\log n)$ time according to the tutorial here. However I'm not able to prove ...
1
vote
1answer
22 views

How to compute time complexity of a program if the time complexity of a function called inside a loop is known? [duplicate]

This is the question- Let $A[1,....,n]$ ba an array storing a bit $(1\,\,or\,\,0)$ at each location, and $f(m)$ is a function whose time complexity is $\theta(m)$. Consider the following program - ...
0
votes
3answers
50 views

Can the runtime of functions with no loops change with the number of calls?

How can we perform time complexity analysis on a function that has no loops? int somefunction(int param) { if (something) do this; else do this; } ...
2
votes
1answer
39 views

Precise runtime of the algorithm to find number of digits in an integer

Consider an integer ( of arbitrary length ). To find the number of digits it has, here is a known simple algorithm ...
1
vote
2answers
251 views

Why does randomized Quicksort have O(n log n) worst-case runtime cost?

Randomized Quick Sort is an extension of Quick Sort in which pivot element is chosen randomly. What can be the worst case time complexity of this algo. According to me it should be $O(n^2)$. Worst ...
3
votes
1answer
56 views

Heapsort for sorted input

What is the running time of heapsort when the input array is in increasing order? How about decreasing order? (I came across these questions in CLRS.) Here is what I have done so far ... For the ...
1
vote
1answer
43 views

What is the correct representation of Master Theorem?

What I'm taught in my class - $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$ where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$ if ...
-3
votes
1answer
54 views

Complexity Analysis for a nested loop with two methods [duplicate]

Hey I am studying for my intro algorithms class final and I'm not sure if I'm understanding this question correctly (its from a sample final exam). If someone could explain this to me that would be ...
1
vote
2answers
61 views

If algorithm runs $\theta(n)$ in time T, doubling input size has what effect on time T?

In other words, is there a relationship between the step size and the actual running time? Suppose that the algorithm is run on identical machine.
-1
votes
3answers
50 views

How to find upper and lower bound without using formula

I'm studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything useful. Prove the following sum is $\Theta (n^2)$ (we have to find ...
4
votes
1answer
53 views

Why is the running time of edit distance with memoization $O(mn)$?

I understand without memoization it is going to be $O(3^{\max\,\{m,n\}})$ because every call results in extra three calls: thus we end up having a call tree with three children for each node, with ...
6
votes
2answers
199 views

algorithm time analysis “input size” vs “input elements”

I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm Seems that input length for the algorithm ...
1
vote
1answer
49 views

Amortized analysis of virtual, dynamic array using potential function

You often want to implement an array $A$ where the length fluctuates over time. If at some point $A$ has length $n$, then you would like to use space $O(n)$. Consider the following: At all moments, a ...
6
votes
4answers
726 views

Is there a method for automatic runtime analysis of algorithms?

I am wondering, is there a method for automatic runtime analysis that works at least on a relevant subset of algorithms (algorithms that can be analyzed)? I googled "Automatic algorithm analysis" ...
0
votes
0answers
21 views

Nested Loop Complexity [duplicate]

I have several lists of varying size, each index of the list contains both a key and an object : list1.add('Key', obj). The lists are all sorted. My aim is to iterate through the list and match 1 or ...
3
votes
1answer
39 views

Asymptotic expected runtime of Randomized Algorithm

I am analyzing the asymptotic runtime of a randomized algorithm in expectation. The algorithm has the following properties: Given input size $n$, with probability $3/4$ it moves on to solve an ...
5
votes
1answer
441 views

Would using the mean as pivot speed up quicksort?

Somehow I thought about quicksort last night and was reading about it on Wikipedia. The interesting part for me was: 'If we could consistently choose a pivot from the middle 50 percent, we would only ...
1
vote
0answers
88 views

Running time analysis of a segment tree

Can someone provide an analysis of the update and query operations of a segment tree? I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and ...
9
votes
2answers
112 views

Multiplication in $O(n\cdot \log n)$

I was looking in here, and I noticed the best runtime for multiplication of two $n$-bits numbers is $O(n\cdot \log n \cdot 2^{O(\log^* n)}$, but I can easily notice an algorithm that runs in $O(n\cdot ...
2
votes
1answer
47 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 ...
5
votes
1answer
48 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 ...
0
votes
0answers
39 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 ...
1
vote
1answer
69 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 ...
2
votes
1answer
26 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 ...
1
vote
0answers
34 views

Is this Time analysis strategy right?

I'm working in the time analysis for an algorithm with two optional optimizations variant applied and followed next approach: Create inputs of different lengths for the algorithm Using these inputs ...
0
votes
1answer
33 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
vote
1answer
80 views

Time/Space cost of Taxicab algorithm?

The following is an algorithm for generating "Taxicab numbers" using a priority queue (pq). Vector is an arbitrary data type ...
0
votes
0answers
45 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 ...
2
votes
1answer
89 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
21 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 ...
1
vote
2answers
34 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
90 views

Find all $k$ local maximums in an array of length $n$ in $O(n \log k)$ time

Given a sequence of numbers $a_1, a_2, ..., a_n$, a number $a_i$ is called the $k$ local maximum $\iff i > k$ and $a_i$ is the largest number among the $(k+1)$ numbers $a_{i-k}, a_{i-k+1}, ..., ...
0
votes
1answer
74 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 > ...
1
vote
2answers
50 views

Proving the lower bound of compares in comparison based sorting

I'm reading Sedgewick and Wayne's book of Algorithm. When I read the following proof in the attached picture, I don't understand why it assumed the comparison number is lg(number of leaves). Any help ...
1
vote
1answer
76 views

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?

How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? (where n is a power of 3) I was told it takes: $$2(n-2) + 1 = 2n-3$$ However, I can't seem to figure out ...
1
vote
1answer
40 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 ...
8
votes
1answer
230 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
votes
1answer
99 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. ...
1
vote
2answers
81 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 ...