# Big O Problem

Not what you're looking for?

Show that if:

T(1) = a

T(n) = T(n-1) + n^k, for n > 1

then T(n) is O(n^(k+1)). You may assume k>=0. Also, show that this is the tightest simple big-oh upper bound, that is, that T(n) is not O(n^m) if m < k+1. Hint: Expand T(n) in terms of T(n-i), for i = 1,2,..., to get the upper bound. For the lower bound, show that T(n) is at least cn^(k+1) for some particular c >0.

##### Purchase this Solution

##### Solution Summary

Big O Problem is solved.

##### Purchase this Solution

##### Free BrainMass Quizzes

##### Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.

##### Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

##### Javscript Basics

Quiz on basics of javascript programming language.

##### Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

##### Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.