Data Structures and Algorithms
Primary version
Primary version
  • Data Structures and Algorithms
  • Algorithms Analysis
    • Measuring Resource Consumption
    • Growth Rates
    • Asymptotic Notation
    • Analysis of Linear Search
    • Analysis of Binary Search
    • How to do an analysis in 5 steps
  • Recursion
    • Writing a recursive function
    • How do recursive functions work?
    • Analysis of a Recursive Function
    • Drawbacks of Recursion and Caution
  • Lists
    • Implementation
    • Linked List
      • Concepts
      • Implementation - List and Nodes
      • Implementation - push_front(), pop_front()
      • Implementation - Iterators
      • Modification - Sentinel Nodes
  • Stacks and Queues
    • Stack Implementation
    • Queue Implementation
  • Table
    • A Simple Implementation
    • Hash Tables
      • Bucketing
      • Chaining
      • Linear Probing
  • Sorting
    • Simple Sorts
      • Bubble Sort
      • Insertion Sort
      • Selection Sort
    • Merge Sort
    • Quick Sort
    • Heap and Heap Sort
      • Priority Queues using Binary Heaps
      • Heapify and Heap Sort
  • Trees
    • Binary Trees
    • Binary Search Trees
    • BST Implemenation
    • Iterative Methods
    • Recursive Methods
  • AVL Trees
  • Red Black Trees
  • 2-3 Trees
  • Graphs
  • Introduction to Computational Theory
  • Appendix: Markdown
  • Appendix: Mathematics Review
Powered by GitBook
On this page
  • What is Algorithms Analysis

Algorithms Analysis

What is Algorithms Analysis

When you write a program or subprogram you should be concerned about the resource needs of the program. The two main resources to consider are time and memory. These are separate resources and depending on the situation, you may end up choosing an algorithm that uses more of one resource in order to use less of the other. Understanding this will allow you to produce better code. The resource to optimize for depends on the application and the computing system. Does the program need to finish execution within a restricted amount of time? Does the system have a limited amount of memory? There may not be one correct choice. It is important to understand the pros and cons of each algorithm and data structure for the application at hand.

The amount of resources consumed often depends on the amount of data you have. Intuitively, it makes sense that if you have more data you will need more space to store the data. It will also take more time for an algorithm to run.

Algorithms Anaylsis does not answer the question "How much of a resource is consumed to process n pieces of data"... the real question it answers is "How much more of the same resource will it consume to process n+1 pieces of data"

In other words what we really care about is the growth rate of resource consumption with respect to the data size.

And with this in mind, let us now consider the growth rates of certain functions.

PreviousData Structures and AlgorithmsNextMeasuring Resource Consumption

Last updated 3 years ago