[Solved] How do I prove or disprove that this function is Ω(n^1.5)?

Assuming that T(n) doesn’t suddenly become negative at some value of n, we can give a lower bound for the left hand side if we neglect the first term:

We define a new function S(n) such that:

We can immediately see that it has terms (ignoring off-by-one etc.). Thus if we keep expanding:

At this stage, since we know that log(n) << n for any large n, we can apply a Taylor expansion to the third term in the recursive call to S(n):

We can realistically ignore the 2nd term too. Applying this approximation to every S(n) call:

Now, we know that:

b obviously can be 1.5; therefore:

---

EDIT: some numerical tests to confirm this result –

Code:

uint64_t T(int n) {
  return n <= 1 ? 0 : T(n - log(n)) + T(log(n)) + (uint64_t)n;
}

Results:

N           T(N)
--------------------------
2           2
4           6
8           18
16          60
32          181
64          578
128         1911
256         6331
512         22011
1024        79304
2048        279719
4096        1016217
8192        3814210
16384       13902832
32768       51540129
65536       195366441
131072      732435510
262144      2744988819
524288      10457580914
1048576     39910628826

Plot of N^2/log(N) against T(N):

The relationship is linear, meaning that

… confirming the given result.