C.5. Upper Limit on Sum of a Function

Table of contents:

We often deal with monotonically nondecreasing functions, such as running-time functions for algorithms. It is easy to state an upper limit on a sum of applications of such a function.

Figure C-4 shows why this is true.

Figure C-4. Since f(n) i) for any i < n, the sum falls within an f(n) x n rectangle.



C 6 Constant Factors

Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

Part II: Linear Structures

Stacks and Queues

Array-Based Structures

Linked Structures

Part III: Algorithms

Analysis of Algorithms

Searching and Sorting

Recursion

Part IV: Trees and Sets

Trees

Sets

Part V: Advanced Topics

Advanced Linear Structures

Strings

Advanced Trees

Graphs

Memory Management

Out to the Disk

Part VI: Appendices

A. Review of Java

B. Unified Modeling Language

C. Summation Formulae

D. Further Reading

Index



Data Structures and Algorithms in Java
Data Structures and Algorithms in Java
ISBN: 0131469142
EAN: 2147483647
Year: 2004
Pages: 216
Authors: Peter Drake

Flylib.com © 2008-2020.
If you may any questions please contact us: flylib@qtcs.net