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
12 views

How to determine big O of a variable loop

I want to classify the runtime of this function in big O notation. This function is multiplying two whole numbers and checks the in binary digits of the multiplicand. And adding the multiplier to the ...
1
vote
0answers
16 views

Analysis of Weighted Quick Union with Path Compression

I have searched the internet for an analysis of why WQUPC is amortized $O( m \alpha (n) ) $ for m operations on n nodes ( $\alpha ( n) $ is the inverse Ackerman function). I understand why it is $O ( ...
-1
votes
2answers
54 views

Question about time-complexity for MST-like algorithm

I have got a problem with an excercise about graphs: Your friend has been hired by a brewery to work out the most efficient delivery route for the beer-delivery truck drivers. A typical delivery has ...
-1
votes
1answer
34 views

How fast can one compute the power of a number?

Let $x \in \mathbb{R}$ and $k \in \mathbb{Z}^+ \cup \{0\}$ then how fast can one compute $x^k$? If $x, k \in \mathbb{Z}$ then I guess this previous discussion already settled that, How many ...
5
votes
1answer
67 views

A* graph search time-complexity

Some confusion about time-complexity and A*. According to A* Wiki the time-complexity is exponential in the depth of the solution (shortest path): The time complexity of A* depends on the ...
3
votes
2answers
95 views

What is running time of an algorithm?

What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the ...
1
vote
0answers
52 views

Calculating number of operations in a divide and conquer approach when the input is not an exact power of 2

Here is a divide and conquer approach for finding minimum and maximum elements in an array. ...
8
votes
1answer
64 views

What is the complexity of a bracketed search using mediants?

I'm trying to estimate the complexity of an algorithm I've written for the Reko decompiler, where I'm trying to "undo" the tranformation done by a compiler to an integer division by a constant $x / ...
3
votes
2answers
488 views

How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?

How are asymptotical time complexities calculated for recursive algorithms? Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they ...
2
votes
1answer
48 views

Costs of updating arrays to contain only zeroes

To initialize an array of length $n$ has complexity $O(n)$, as far as I understand. If I set every element to zero (with one code line), does that have time complexity $O(n)$ also? And in that case, ...
1
vote
2answers
38 views
0
votes
2answers
27 views

What is the asymptotic running time of the following piece of code? [duplicate]

I am working with this problem: What is the asymptotic running time of the following piece of code? ...
5
votes
1answer
56 views

How to find time complexity for functions in lazy functional languages?

So far, I have looked around the internet for information how to find the time complexity for functions in lazy functional languages, but most of the resources on time complexity focus on strict ...
1
vote
0answers
45 views

Runnig time analysis for algorithem that merges $k$ sorted arrays to one sorted array

Given $k$ sorted arrays, the size of each array is $n$ and we want to sort them to one sorted array. assume that $k=2^p$ i.e $k\in\{ 2^1,2^2,2^3,2^4,\dots\}$ I the first step we will merge ...
0
votes
0answers
31 views

Frequency count of while loop [duplicate]

I'm task to solve a problem in UVA and its problem 305 in particular well its easy to program it just brute forcing stuff. Part of the task is to find the big Oh of the program using frequency count ...
-2
votes
0answers
18 views

Cost of inserting a sequence of numbers into a BST one by one and then right-rotating all

Is the best case time complexity for a procedure that inserts one by one a sequence of numbers into a BST and then that right-rotates the nodes(all of them) of the BST Θ(n), average case Θ(n logn) and ...
2
votes
1answer
107 views

Does my simple, static hash table have O(1) worst case lookup?

Will the following simple hash table construction algorithm be able to construct a static hash table in $O(n)$ expected time, and will the worst case access time be $O(1)$? If not, what are the ...
3
votes
3answers
395 views

Are there adversarial inputs for randomized quicksort?

Someone recently claimed that there's an adversarial input for randomized quicksort; he referenced this paper. This defies my intuition because there are results that say that randomized quicksort ...
0
votes
2answers
389 views

how to calculate time complexity of non terminating loops

I'm studying about data structures and algorithms in that Time complexity and calculating time complexity of the programs. I just wondered that how to calculate time complexity of non terminating ...
3
votes
1answer
57 views

Explanation of a simple algorithm's Big O complexity

I'm looking at a past paper, where there is the following Algorithm, and we are asked to give the runtime in O notation: ...
-3
votes
0answers
9 views

big o complexity analysis of dependent nested loops [duplicate]

for(i=0;i<=n;i++) { for(j=0;j please help me in finding complexity of this nested loop.... the outer loop is executing n times and inner loop is dependent on the value of i. so what will be its ...
4
votes
2answers
115 views

What data structure might this game use?

This question is not about game development or about actual implementation details. I was playing Little Alchemy yesterday. (Warning: Productivity hazard.) You start with the four classical ...
2
votes
0answers
22 views

Byte Code/IL Code execution [closed]

I understand that Byte/ IL Codes are interpreted/executed by their corresponding run times. Do those run time converts the Byte/IL codes directly to machine code which processor can execute or the ...
7
votes
3answers
476 views

The difference between theoretical complexity and practical efficiency

If I have this pseudocode: for i=0 to n/2 do for j=0 to n/2 do ... do anything .... The number of iterations is $n^2/4$. What is the complexity of ...
1
vote
1answer
41 views

Runtime of algorithem when the internal for depend on the external for

I'm trying to find the running time of this pseodocose: int x=0,i,j for (i=1;i<=n;i++) for(j=1;j<=n+r;j=j+i) x=x+j; What I did: First I checked ...
3
votes
1answer
27 views
2
votes
2answers
35 views

Running time of selection sort

I wrote pseudocode for Selection Sort, but I'm not sure what is the running time of my algorithm, can you help me with that? My Pseudocode: Selection Sort(int ...
1
vote
2answers
61 views

How to calculate the mergesort time complexity?

Recently while reading a book I came across the following statement: Mergesort works by dividing nodes in half at each level until the number of nodes becomes 1 hence total number of times we ...
2
votes
0answers
46 views

Computational complexity of Doolittle's algorithm

I could not find a big-oh cost for Doolittle's algorithm for LU decomposition of a matrix online, so I took a pseudocode implementation from here and analyzed it to get ...
13
votes
3answers
2k views

How long does the Collatz recursion run?

I have the following Python code. ...
1
vote
1answer
31 views

Complexity for merging 3 sorted arrays using this specific algorithtm

During an interview I was asked to calculate the big theta complexity for the following algorithm that receives 3 sorted arrays of variable size and returns a new array which has the elements of the ...
0
votes
1answer
59 views

sorting a sorted array that has been inc/dec by random numbers

If given a sorted array of n distinct positive integers. And each element is incremented or decremented by a number between 0 and X. For positive integer X that is a function of n. Formulate an ...
3
votes
1answer
48 views

Analysing a small recursive algorithm

I need to calculate the complexity of func5, depending on variables $n, m$. func4 is a function whose complexity is $\Theta(n+m)$ ...
1
vote
2answers
80 views

What is the significance of a Θ-bound on the running time of Mergesort?

While studying algorithm analysis I found that there is something called tight bound and there is some mathematical formula to support it. Given: Mergesort takes $\Theta(n \log n)$ compares to ...
1
vote
1answer
83 views

Big Omega of a while loop

I am learning about running times now and I am having trouble wrapping my head around Big Omega time. So, its safe to say that Big Omega of binary search is Ω(1), ...
0
votes
1answer
45 views

Rate Monotonic First Fit vs. Rate Monotonic Next Fit vs. Proportionate Fair

What would an example of a set of tasks be, where RMFF, RMNF and P-Fair all result in a different number of processors required?
3
votes
3answers
327 views

Calculating time complexity of a code which may be incorrect

I am a sophomore taking a course in algorithm analysis. We were asked by our professor to calculate time-complexity of several C functions, but some of them were incorrect and would result in a ...
0
votes
2answers
316 views

Runtime for algorithm

I need to get the asymptotic runtime for an algorithm and I'm just stuck. A python implementation: ...
1
vote
1answer
28 views

General question on approach to showing sample size required is $\Omega(\cdot)$

I was not able to find a similar question in the archives, so pardon this relatively elementary question if it has been asked before. Let $E_n$ be some event that depends on the sample size $n$ and ...
0
votes
2answers
52 views

Running-time cost of Tweaked Nested Loop

I understand that the following nested for-loop: for(i=0; i<n/2; i++) for(j=0; j<n/2; j++) print(j) has the runtime complexity of which ...
3
votes
2answers
73 views

Insertion sort with pairs of numbers already in order

I am currently attempting to work out the number of comparisons that is done by insertion sort when the elements are already in sorted pairs, for example $$4,5,22,23,1,2,19,20, \dots$$ Currently ...
6
votes
2answers
637 views

Why is the dynamic programming algorithm of the knapsack problem not polynomial? [duplicate]

The dynamic programming algorithm for the knapsack problem has a time complexity of $O(nW)$ where $n$ is the number of items and $W$ is the capacity of the knapsack. Why is this not a polynomial-time ...
1
vote
0answers
31 views

Deterministic Selection Median of Medians [duplicate]

As I understand, a quick-select algorithm could use median of medians to find best suited pivot to yield the i-th item in the array, say A. I have referred to Median of Medians algorithm and steps ...
1
vote
1answer
103 views

Complexity of dynamic card game algorithm

Consider the following dynamic card game with a regular deck of 26 red cards and 26 black cards. A dealer draws the unturned cards one by one, and we can ask him to stop at any time. For every red ...
3
votes
2answers
104 views

Identifying system events affecting timing behavior of an application

Q: What are those events (system level and architecture level) that can cause an application to take longer to terminate and complete the job? My question is purely in the context of Worst Case ...
0
votes
0answers
17 views

How to show the running time of the following algorithm? [duplicate]

The outer loop runs $n$ times. The inner loop runs $\lfloor \frac{n}{i} \rfloor$ times. So it would be $O(n \cdot \lfloor \frac{n}{i} \rfloor)$. I do not know how to transform that into a proper ...
0
votes
0answers
57 views

Analyzing a sorting algorithm [duplicate]

Each of n distinct values is equally likely to be put into pile 1 or in pile 2, independent of each other. These piles are then sorted from smallest to largest. The two sorted piles are then merged ...
0
votes
1answer
46 views

Differentiating between BubbleSort and InsertionSort

This is a homework I'm doing, but I couldn't find an answer, hopefully you guys can shine some light on this. The problem is this: You have two unknown sorting algorithms, one is Bubble Sort, the ...
-1
votes
1answer
73 views

How do I analyze Mergesort that uses Insertion Sort for small inputs?

I know that Insertion Sort is faster when size $N$ is a small number, hence by modifying Merge Sort to use Insertion Sort when size $N$ reaches $K$, can help improve the performance. How do I ...