Data Structures, Algorithms, & Applications in C++
Chapter 3, Exercise 15
- (E5)
-
(sum from 1 to n)ik <= (sum from 1 to n)nk
= nk+1. Therefore,
(sum from 1 to n)ik = O(nk+1). Further,
(sum from 1 to n)ik >= (sum from n/2 to n)(n/2)k
= (n/2)k+1. Therefore,
(sum from 1 to n)ik = Omega(nk+1).
(Note that 2k+1
is a constant as k
is a constant.)
Consequently,
(sum from 1 to n)ik = Theta(nk+1).
- (E6)
-
(sum from 1 to n)ri = (rn+1-1)/(r-1) - 1
= Theta(rn).
From this it follows that
(sum from 1 to n)ri = O(rn) and
(sum from 1 to n)ri = Omega(rn).