CODEWITHSUNDEEP
algorithmmathbig-o
user31641
user31641

Reputation: 175

Confusion related to Big O

I was working on space and time complexity and came across this

O(n + (n/2 + n/4 .... n/n)) = O(n + log(n)).

I didn't get how this is true? Can anyone please provide some insights?

Upvotes: 1

Views: 52

Answers (1)

templatetypedef
templatetypedef

Reputation: 372784

I think this depends on your denominators. The summation

n + n / 2 + n / 4 + n / 8 + ... + n / n

sums out to O(n), since it's equal to

n (1 + 1/2 + 1/4 + 1/8 + ...)

≤ 2n

Therefore, it's technically correct that it's O(n + log n) because O(n + log n) = O(n), but that's a very strange way to write it. O(n) is a much better way to write this out.

The summation

n + n/2 + n/4 + n/6 + n/8 + ... + n / n

works out to

n (1 + 1/2 + 1/4 + 1/6 + 1/8 + ... + 1/n)

= n (1 + (1/2) * (1 + 1/2 + 1/4 + 1/6 + ... + 1/(n/2)))

= n (1 + (1/2)H_{(n/2)})

= Θ(n log n)

This works because the nth harmonic number is Θ(log n). That's probably closer to what was intended, but with + replaced with ×.

Hope this helps!

Upvotes: 7

Related Questions