הפונקציה T ( n ) {\displaystyle \displaystyle T(n)} נתונה על ידי הנוסחה. T ( n ) = ∑ i = 1 n ∑ j = i n [ Θ ( j − i + 1 ) ] {\displaystyle \displaystyle T(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]} .
אנא הוכח T ( n ) = Θ ( n 3 ) {\displaystyle \displaystyle T(n)=\Theta (n^{3})} .
רמז
נסה להוכיח זאת באותו אופן בו הוכחנו ∑ i = 1 n [ log ( i ) ] = Θ ( n ⋅ log ( n ) ) {\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=\Theta (n\cdot \log(n))} . כלומר:
נתונה על ידי הנוסחה.
![{\displaystyle \displaystyle T(n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e0ad48d0a33c3eee7f7d75e88bd699636abf44e1)
.
.
![{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=\Theta (n\cdot \log(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f116613809a87640ad4c06e60144f9545fa8ad6)
. כלומר:
ו
.