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
2answers
5k views

Time complexity to check if there is an edge between two nodes in an adjacency list

I know that the time required to check if there exists an edge between two nodes in an adjacency matrix is $O(1)$ because we can access it directly (i.e: $M[i][j]$). However, I didn't really get why ...
0
votes
1answer
31 views

Computation time of a Binom matlab (or C) routine

I am trying to write a Matlab (or C) routine for the exact probability F of observing K or more successes when a success probability P is expected ($\sum_{k=i}^n \binom{n}{k}p^k(1-p)^{n-k}$). I am ...
0
votes
0answers
174 views

Recursive euclid algorithm for gcd complexity [duplicate]

I am trying to calculate the complexity of the euclidean algorithm for finding the greatest common divisor (gcd) (recursive version). Here's the pseudo code: ...
3
votes
1answer
40 views

Saving time finding a result by guessing first?

I am currently taking a graduate course about Image Processing in electrical engineering and while this question doesn't particularly relate to the class itself but rather some concepts in the ...
2
votes
0answers
690 views

DPLL time complexity analysis

Consider the most naïve backtracking for CNF-SAT. It only checks if an assignment satisfies the input formula $\phi$ when all the $n$ variables have values assigned. Let $m$ be the size of $\phi$. ...
0
votes
1answer
62 views

Intuitive way to understand “Run-Length Encoding”

Run-Length Encoding is the simple form of lossless data compression in which compression in which runs (execution) of data are stored as a single data value and count rather than as the original run (...
0
votes
0answers
197 views

Doubt on analysis on time and space complexity of creating n² tuples

This is a question from a past-yr mid-term paper from my school(using Python language). Attached below is a diagram to show how a robot will move. Don't mind if the link seems dubious as I just used ...
2
votes
1answer
226 views

Exact Analysis of the Merge Sort

When doing the "inexact" analysis of the Merge Sort, the literature that I have seen usually consider that the input is an array with a even quantity of numbers and the recurrence relation is: $T(n) =...
8
votes
1answer
126 views

What counts as an operation?

Apologies for the newbie question, but I am a bit confused about what exactly counts as a "simple operation" when working out the time complexity of an algorithm. In particular, why do we consider all ...
0
votes
2answers
49 views

Is every algorithm on bounded resources O(1)

Suppose that I have a restricted Turing Machine - it has finite tape and takes bounded input. Consider a program that halts on every input (which is at most $k$ bits). The set of inputs is finite, ...
1
vote
2answers
5k views

Time complexity of Prim's algorithm

There is this Prim's algorithm I am studying, the time complexity of which is $O(n^2)$ (in the adjacency matrix). As far as I have understood,that is because we have to ckeck all the nodes per every ...
-1
votes
2answers
11k views

What is the time complexity of the following program?

Please help me calculate the time complexity of the following program. int fun (int n) { if (n <= 2) return 1; else return fun(sqrt(n)) + n; } ...
0
votes
2answers
23 views

Runtime analysis of bit operations

In class we have learned that division takes O($k^2$) where k is the bitlength of the numbers used in the operation. What would be the runtime of a function that looks like this? ...
-1
votes
2answers
102 views

Big-O notation analysis [duplicate]

Can I get help to give an analysis of the running time Big-O? I'm not sure if all my answers are correct. I got for a) $ O(n)$, b) $O(n^3)$, c) $O(n^{1/2})$ and d) $O(log(n))$ ...
0
votes
0answers
215 views

Time complexity of inorder run on B+ tree (without leavesa link)

I quite sure that it should be $O(n)$, but I didn't found any information about it and I'm not sure how to prove it. Maybe in 2-3 tree the max number of node (include the leaves) is $2n$ and in each ...
1
vote
1answer
165 views

Cost of break statement

i am trying find the Cost of an algorithm. it contains break statements. is there any cost of break and Continue statement in a Algorithm?
1
vote
2answers
737 views

Time complexity of euler totient function

Code for finding $\phi$(n) is ...
1
vote
2answers
240 views

Confusion over the complexity of parameter passing in merge sort

I'm working through CLRS on problem 4-2, which says the following: Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an $N$-element array is ...
1
vote
2answers
682 views

Solving complexity using summation

I have the following algorithm: func() { for(i=1; i<n; i=i*2) print("aa"); } How can I find Big-Oh using summation?
0
votes
1answer
320 views

Amortized time of insertion into an Array list

According to Amortized time cost of insertion into an Array list, A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we'...
1
vote
2answers
1k views

EXTRACT MIN algorithm for Young tableau

This are two sections from a task I got. The Young tableau is defined as a matrix of m rows on n columns so that the bars in each row are sorted in ascending order Left to right and the ...
0
votes
1answer
45 views

Can I assume that a percentage of the time can be parallelized?

I study computer science and hardware. Some problem are about parallel computing and applied Amdahl's law. For instance, some calculation is that the sequential part of a program takes x seconds and ...
1
vote
1answer
611 views

Complexity of while loop using series

For the following code fragment: i = 1; s = 1; while(s <= n) { i++; s = s+i; printf("x"); } How can we go about proving the time complexity of ...
0
votes
1answer
95 views

Complexity of a loop

If the body of a simple for loop has time complexity $O(n)$ and it is executed $n-1$ times what is the time complexity of the complete loop? I am trying to figure out the correct answer to this ...
1
vote
2answers
2k views

Big O notation for recursive algorithm [duplicate]

In order to find Big O for a recursive algorithm, it is needed to know the stopping criteria of that algorithm. For the recursive algorithm to find Factorial of a number it is very easy to find the ...
3
votes
0answers
963 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 ( ...
0
votes
2answers
190 views

Why and how geometric series are used for proofs?

I often see that someone uses geometric series for proofs related to time complexity, but also I can't understand why they are used. Are they making proving easier? And how can I use this 'tool' for ...
0
votes
0answers
83 views

How many operations does this algorithm require?

I have the following algorithm x = 0 S = {} k = 1 while x + a[k] < n do S = S + {k} x = x + a[k] k = k + 1 end where ...
0
votes
0answers
199 views
1
vote
1answer
52 views

Runtime analysis of bit sorting algorithm with input size and integer size

I'm struggling to analyze the runtime of this algorithm mainly because it depends on two parameters - the length of the input n, and also the bit size of individual n (bitnum). Most documentation I ...
1
vote
1answer
563 views

A plane-sweep algorithm for a points in triangles inclusion problem

I was given the following homework assignment: Consider a set of $p$ points and $t$ triangles in the plane. The triangles are pairwise disjoint, that is, their edges do not intersect, no triangle ...
2
votes
1answer
2k views

Recursion call inside a for loop time

I'm analyzing a piece of code that has a recursive call inside a for loop such as: ...
0
votes
0answers
75 views

Time Complexity — Recursion

It's been a long time since I've studied time complexity in school, but I've been tasked with finding the time complexity of an algorithm. Here is the algorithm in a pseudo-pseudocode (yes, two ...
0
votes
1answer
55 views

How could a total asymptotic runtime exceed the upper bound of an algorithm's runtime?

This question is specifically related to https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm The $gcd(x,y)$ is solved in $O(T(n) log n)$, where $n$ is the number of bits ...
2
votes
0answers
72 views

A question on analysis of the time complexity of a recursive branching algorithm

I'm reading papers on algorithms of maximum independent problem and the basic recursive branching rules is as follows: Let $G(V,E)$ be an $n$-node undirected, simple graph without loops, and $\...
0
votes
0answers
243 views

Analysis of finding the k-th largest element in a subsegment of an array

Given an array $A$ of length $N$. There are $Q$ queries, each queries will be in the form ...
0
votes
1answer
422 views

What is the time and space complexity of Rete algorithm

I am working on pattern matching algorithm. Its working and using very less memory. For the comparison, I have to compare it with the Rete Algorithm. I have checked it in the thesis of the author, ...
0
votes
2answers
1k views

Running time with while loop

What's the running time of: foo(n) if(n==1) return; int i=1; while(i<n) { i=i+2 } foo(n-2) There are $n/2$ recursive calls to ...
3
votes
1answer
2k views

Why is a sequence of n Push, Pop, Multipop operations O(n²)?

From "Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein, Third Edition, page 453: Let us analyze a sequence of $n$ Push, Pop, Multipop operations on an initially empty stack. The ...
5
votes
5answers
1k views

Why call it 'Time Complexity'?

P.S. I have added the tag 'history', if there is any historical connotation. Also, I found this question What is running time of an algorithm? but I am not satisfied with answers.
0
votes
1answer
199 views

Psedu-polynomial Time : Conflict with the definition of input size

From wikipedia In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required ...
0
votes
0answers
52 views

What kind of runtime behavior should we expect of Finite Element Methods?

For a typical finite element algorithms, what kind of order of growth in solution time (i.e solve stiffness matrix & post-processing) are we expected to see with an increase in number of elements? ...
0
votes
1answer
83 views

Theta Manipulation to show $N = \Theta(n/\log N)=\Theta(n/\log n)$

I am studying different models of computation and how algorithms can be interpreted under different models. Here is a math(?) question that has been bugging me. Suppose we have $n = \Theta(N\log N)$ ...
0
votes
1answer
368 views

Finding the average time complexity for a max algorithm

I'm trying to find the average-case number of times that max is assigned a value by the below algorithm find_max. ...
2
votes
0answers
82 views

Examples of context-free grammars with worst-case complexity

What are some examples of context-free grammars that necessarily trigger cubic worst-case complexity for GLR parsers? I have seen a mention of the example S $\rightarrow$ SSS | SS | "a" but I would ...
2
votes
1answer
624 views

Recursive functions from O(n) complexity to O(log n)

For some recursive questions that require recursing on an input with a small piece removed (hence linear in the size of the input), can we reduce run time by recursing on two halves of the input each ...
0
votes
2answers
112 views

Good reference for average-case runtime analysis of QuickSort

I'm a beginner in programming with little knowledge about the technicalities. I'm assigned to do a "reading project" on the average case analysis of quicksort. I mean I have to present it in class. ...
35
votes
2answers
11k views

Why is the log in the big-O of binary search not base 2?

I am new to understanding computer science algorithms. I understand the process of the binary search, but I am having a slight misunderstanding with its efficiency. In a size of $s = 2^n$ elements, ...
2
votes
1answer
45 views

Finding running time

Apologies for this simple question. I found it in the book Algorithms by Sedgewick and Wayne. Give a formula to predict the running time of a program for a problem of size N when doubling experiments ...
0
votes
0answers
106 views

Linear time reduction equivalence

I have to show if the following statement is true or false. Suppose we have two problems $A$ and $B$. We want to know whether the following is true: If $A \le_p B$ and there is an algorithm which ...