Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Questions tagged [runtime-analysis]

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

791 questions
Filter by
Sorted by
Tagged with
1answer
12 views

### Necessary conditions for proving If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))

I am learning about algorithmic complexities and I read that if f(n) and g(n) are asymptotically positive functions and if $f(n) =O(g(n))$ then the relationship $log(f(n)) = O(log(g(n)))$ holds. I ...
0answers
20 views

### time complexity of 2 sum problem using binary search

this is a popular searching problem and the question is : Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The ...
0answers
17 views

### Do problems that have unary encodings automatically become unary languages?

This problem has confused me a lot, can any of you help me out. Thank you.
0answers
24 views

1answer
26 views

3answers
86 views

### What should I call algorithms with non-linear non-constant time?

I am writing a paper in which I want to refer to a group of algorithms. Some of these algorithms are of complexity O(NlogN), and some of the are more complex (e.g ...
2answers
229 views

### 3 * O(n^2) vs O(n^3)

Currently while I was coding, I got a doubt. While I was solving a particular type of problem I found it to be solved in $O(n^3)$. I have broken that problem and solved it in $O(n^2)$. But to ...
0answers
19 views

### Run time of pseudo code in big theta notation [duplicate]

I am looking for the run time of the following pseudo code. ...
1answer
78 views

### Worst Case Scenario for Quicksort algorithm with pivot element n/2

What would the worst case array look like if I decide to always take the element on the position $\frac{n}{2}$ as the pivot element? I know that if I choose the left or rightmost element as pivot ,the ...