# Big O problem

Not what you're looking for?

Consider the recurrence

T(1)=a

T(n)=cT(n/d)+bn^k, for n a power of d

Iteratively expand T(n) in terms of T(n/d^i) for i=1,2,.... Show that

a) if c > d^k, then T(n) is O(n^logd c)

b) if c = d^k, then T(n) is O(n^k log n)

c) if c < d^k, then T(n) is O(n^k)

##### Purchase this Solution

##### Solution Summary

This solution helps with a software development problem.

##### Purchase this Solution

##### Free BrainMass Quizzes

##### 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.

##### C++ Operators

This quiz tests a student's knowledge about C++ operators.

##### Javscript Basics

Quiz on basics of javascript programming language.

##### C# variables and classes

This quiz contains questions about C# classes and variables.

##### 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.