# Design and Analysis of Algorithm

## Problems that can be solved by Algorithms

Sorting Selection Bubble Quick Heap Insertion Radix Merge Searching Numerical Methods Combinatorial problem Graphs problem String Processing Problem Binary Search Tree

## Backward Substitution

Backward substitution, like forward substitution, tries to find a pattern from which we can guess a solution that we then prove using other techniques—but now we start with T(n)...

## Forward Substitution

Forward substitution Let’s consider the recurrence T(n) = T(n-1) + 2n – 1 T(0) = 0 The method of forward substitution proceeds by generating the first half-dozen or so...

## Time Complexity

the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input....

## Order of Growth

Let’s assume that your computer can perform 10,000 operations (e.g., data structure manipulations, database inserts, etc.) per second. Given algorithms that require lg n, n½, n, n2, n3, n4, n6,...

## Linear inequality

In mathematics a linear inequality is an inequality which involves a linear function. A linear inequality contains one of the symbols of inequality: < is less than > is...

## Matrices

Matrix A matrix is an ordered set of numbers listed rectangular form. Example. Let A denote the matrix [2 5 7 8] [5 6 8 9] [3 9 0...

## Vectors

A vector is an object that has certain properties. What are these properties? We usually say that these properties are: a vector has a magnitude (or length) a vector...

## Functions and Relations

A relation is any association between elements of one set, called the domain or (less formally) the set of inputs, and another set, called the range or set of...

## Set Theory

Set: A set can be defined as a collection of things that are brought together because they obey a certain rule. These ‘things’ may be anything you like: numbers,...