Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
4 votes
Accepted

Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails

The problem in the question is a good example for two related principles. Thanks to the substitution method in your try 2, you have found $c=b=1$ will enable the induction step for $T(n)\le cn-b$ to ...
user avatar
  • 33.2k
3 votes
Accepted

How to find parameter sets for a big-O expression to be fixed-parameter tractable?

Here is a simple method to find the parameters with respect to which (the problem whose worst runtime is bounded by) a big $O$-expression becomes fixed-parameters tractable (FPT), i.e., bounded by a ...
user avatar
  • 33.2k
3 votes

Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails

Your second idea is good, there is no need to start at $n = 1$: You already proved that for $n\geqslant 3$, $T(n) \leqslant n - 1$. You can now say that since $n-1 \leqslant n$ and since $T(1)\...
user avatar
  • 7,154
3 votes
Accepted

Find the smallest difference between two numbers in a DS in O(1) time

Use an AVL tree with each node having three additional entries $\min,\; \max$, and $\text{closest_pair} = (i,j)$, representing the minimum and maximum values of the tree rooted at that node. At the ...
user avatar
2 votes

Difference between an exact and Big O Notation for worst case runtime

You can’t calculate any runtime except for some very simple model of a CPU. You can calculate the exact number of comparisons, or the exact number of operations moving array elements of a particular ...
user avatar
  • 24.9k
1 vote

Find the smallest difference between two numbers in a DS in O(1) time

I'm assuming that the sets of functions in big-Oh notation refer to the desired worst-case time complexity of the operations. A possible data structure consists of an AVL tree $T$ plus a priority ...
user avatar
  • 22.8k
1 vote

Find the smallest difference between two numbers in a DS in O(1) time

I think this can be done using $(a,b)$-trees storing a bit more information in internal nodes: the minimum difference between two leaves in the subtree; the minimum and maximum values of a leaf in ...
user avatar
  • 7,154
1 vote

Time Complexity of Exponentiation Operation as per RAM Model of Computation

I just want to say first that I'm not an expert, but I find this question interesting. I will focus on integer exponentiation. Like the OP says, intuitively, exponentiation of integers should cost $O(...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible