New answers tagged

1

The transformation: You define $S(m) = T(2^m)$ which is absolutely fine. $T(m) = T(m^{1/2}) + m$, so $T(2^m) = T(2^{m/2}) + 2^m$. Therefore $S(m) = T(2^m) = T(2^{m/2}) + 2^m = S(m/2) + 2^m$. That's the mistake you made, the last term is $2^m$ and not $m$. Try $n = 2^{1024}$: $T(2^{1024}) = T(2^{512}) + 2^{1024} = T(2^{256}) + 2^{512} + 2^{1024}$ and ...


-2

Complexity of above recurrence is O(m) which is O(log m) and now n = 2 ^m so m = log n and hence complexity is O(log log n).


0

$ T(n) = 25T(n/5) + 20(n\log n)^{1.99} $ Note that $(\log n)^m=O(n^\epsilon)$ for all $m,\epsilon\in \Bbb R^+$. In plain words, all polynomials of $\log n$ grows slower asymptotically than all polynomials of $n$. Here we abuse "polynomials" to include functions like $x\to x^k$ for all $k\in\Bbb R^+$ such as $x\to x^{0.618}$ or $x\to x^{2019.46}$. This abuse ...


2

It feels like you're trying to think in terms of pre-defined recipes, rather than just figuring it out by reasoning about the situation. The if statement triggers every time $y$ is a multiple of $n$. So just work out how many different values in $\{1, \dots, n^2+1\}$ are multiples of $n$, and that's how many times the innermost for loop runs. Of course,...


0

An array is the only thing that will get you consistent lookup in constant time. Removal cost: n Insertion cost: n log n Of you can fit your data to a model (I.e. a polynomial) and the size of your elements remains somewhat constant you can have almost constant lookup with log addition/removal


0

O(1+α) is only equal to O(α) when α becomes much greater than 1 and for hash tables that is usually not the case. For a chaining hash table it would typically be around 1 and for an open addressing hash table it would be less than or equal to 1. If α much greater than 1 we would be calling it a hash table any more but rather a bunch of lists that indeed will ...


Top 50 recent answers are included