# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,100 questions
Filter by
Sorted by
Tagged with
65 views

### How to find examples of best cases for sorting algorithms?

I am asked to give a table of 8 elements that are to be sorted by the following algorithms and to produce their best cases. 1) Selection sort 2) Bubble sort 3) Insertion sort 4) Fusion sort If I give ...
43 views

### Substitution method for $T(n) = 2T(7n/10) + O (1)$ [duplicate]

I want to solve $T(n) = 2T(7n/10) + O (1)$ using the substitution method. I think the solution should be $T(n) = O(n\log n)$, but I am having trouble constructing a proof by substitution.
88 views

197 views

### Solving $T(n)=4T(n/2)-1$ without using the master theorem [duplicate]

How can I solve the following recurrence without using the master theorem? $T(n)= 4T(n/2)-1$ for $n>4$ and $T(n)=5$ for $n\le 4$, $n$ is a power of $2$.
124 views

### How do I describe formally complexity of 2-sum problem algorithm?

I have algorithm that finds if there are two elements in sorted array that have sum zero. ...
66 views

### Prove $8^n = Θ(4^n)$

how would I prove $8^n = Θ(4^n)$ is either true or false. I so far have attempted to prove big O but cant find the value of C1
32 views

### Is the time complexity of this function O(n^3)? And O(n) for its memoized solution?

Given this naive recursive function: ...
47 views

163 views

### How to solve equations using big Θ [duplicate]

How would I prove that the statement $10n^3+3n=Θ(n^3)$ is true/false?
859 views

29 views

231 views

### What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there ...
In the context of Upper bounds computaion and Big Oh Notation, I was wondering if the following could be proved... if they are equivalent. $\mathcal{O}((log(n))^{-1}) = (\mathcal{O}(log(n)))^{-1}$ \$\...