Order of Growth Analysis

Question

Am seeking clarification on how the bound of a particular function is being determined.

E.g 1: A(n) = log(2^n) + n^(1/3) + 1000 Would I be right to say that the last 2 terms can be "ignored" as they are insignificant as compared to the first? And thus the bound is O(2^n)?

E.g 2: B(n) = n + (1/2)*n + (1/3)*n + (1/4)*n + ... + 1 I am more uncertain about this one, but I would give a guess that it would be O(n)? 1 is ignored (as per reasoning for 1000 in E.g. 1), that's what I'm sure.

Was also thinking if the fractions in E.g. 2 are modified, such that the denominators run in different patterns instead (e.g. (1/2)*n + (1/4)*n) + (1/8)*n...), would the order of growth be faster/slower than E.g. 2?

Appreciate any guidance available! Thank you!

For B(n) , Take out n common and now you are left with (1+1/2+1/3+...+1/n). It is [Harmonic Series](https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)) and sum of this series upto `n` terms is `log n`. Therefore total complexity is `O(n log n)`. — Sanket Makani, Jan 28 '18 at 08:57
`log X` is `O(log X)` not `O(X)` (well, at least `O(X)` won't be the tightest bound). Read up on log rules, `log X^Y` can be simplified. — Bernhard Barker, Jan 28 '18 at 09:53
Your second question is a duplicate of [Finding Big O of the Harmonic Series](https://stackoverflow.com/q/25905118) / [Asymptotic complexity of T(n)=T(n-1)+1/n](https://stackoverflow.com/q/15656021) — Bernhard Barker, Jan 28 '18 at 09:54
@Dukeling In both questions you have linked, only part of the harmonic series is considered. It doesn't seem to be the case here. Unless the last term `1` is really `(1/n)*n`. — Nelfeal, Jan 28 '18 at 10:01
@Nelfeal ??? As Sanket pointed out, B(n) = n\*(1+1/2+1/3+...+1/n), and the last part of that is **exactly** what both linked questions calculate. 1 = n*(1/n) for n > 0, in maths. — Bernhard Barker, Jan 28 '18 at 10:05
@Dukeling This is ambiguous, at least to me. The ellipsis could mean two things: an infinite series followed by the constant term "1", or the partial sum of the harmonic series up to n, the last term being `(1/n)*n`, which in this case is the term "1". — Nelfeal, Jan 28 '18 at 10:10
@Nelfeal Ellipsis are commonly used in this manner to mean "stop when we get to the value after the ellipsis". If it was meant to mean an infinite series plus a constant, I would expect the series to be in brackets to clearly show that the 1 isn't part of it. — Bernhard Barker, Jan 28 '18 at 10:17

score 1 · Accepted Answer · answered Jan 28 '18 at 09:57

E.g 1: A(n) = log(2^n) + n^(1/3) + 1000

Here log(2^n) = n which is bigger than n^(1/3) so by the property of Order function A(n0 = O(n)

E.g 2: B(n) = n + (1/2)*n + (1/3)*n + (1/4)*n + ... 1
        = n*(1 + 1/2 + 1/3 + 1/4 ....+ 1/n)

Now (1 + 1/2 + 1/3 + 1/4 ....) you can approximate by thinking it is integration of dx/x from 1 to n which comes to be log(n) making the resulting Order = O(nlgn)

E.g 2 Modified = n  + (1/2)*n + (1/4)*n + (1/8)*n +.....
           = n( 1+ 1/2 + 1/4 +1/8...) [GP series]
           = n / (1/(1-1/2))
           = 2n

So it becomes O(n)

Nelfeal · Answer 2 · 2018-01-28T10:07:35.423

E.g 1: A(n) = log(2^n) + n^(1/3) + 1000 Would I be right to say that the last 2 terms can be "ignored" as they are insignificant as compared to the first? And thus the bound is O(2^n)?

If you simplify the expression, you get A(n) = n*log(2) + n^(1/3) + 1000. The last two terms grow more slowly than the first, n*log(2), which is simply O(n). Hence A(n) is O(n).

E.g 2: B(n) = n + (1/2)*n + (1/3)*n + (1/4)*n + ... + 1 I am more uncertain about this one, but I would give a guess that it would be O(n)? 1 is ignored (as per reasoning for 1000 in E.g. 1), that's what I'm sure.

This one is tricky because it involves an infinite series. If you only had n + (1/2)*n + (1/3)*n + (1/4)*n, then it would be equivalent to a*n with some fractional a, and that is O(n). However, since the expression is a divergent infinite series known as the harmonic series, you cannot conclude that B(n) is O(n). In fact, B(n) can be simplified as S_k(1/i)*n + 1 as k tends to infinity, with S_k(1/i) the sum of 1/i with i from 1 to k. And because S_k diverges as k tends to infinity, B(n) also tends to infinity, assuming n>0.

In the end, B(n) in not bounded. It doesn't have a proper order of growth.

Edit: if B(n) does not contain an infinite series but instead stops at (1/n)*n, which is the last 1 in your expression, then the answer is different.

The partial sums of the harmonic series have logarithmic growth. That means that B(n)/n, which is exactly the partial sum, up to n, of the harmonic series, is O(log n). In the end, B(n) is simply O(n log n).

Order of Growth Analysis

2 Answers2