# Questions tagged [runtime-analysis]

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

811 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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: ...
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 ...
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$. ...
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 (...
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 ...
226 views

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 ...
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 ...
199 views

### What is the change in time complexity due to substitution of variables?

This is a question I have after listening to a lecture. ...
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 ...
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 ...
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: ...
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 ...
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 ...