DSA using C Tutorial
Selected Reading
- DSA using C - Discussion
- DSA using C - Useful Resources
- DSA using C - Quick Guide
- DSA using C - Recursion
- DSA using C - Sorting techniques
- DSA using C - Search techniques
- DSA using C - Graph
- DSA using C - Heap
- DSA using C - Hash Table
- DSA using C - Tree
- DSA using C - Priority Queue
- DSA using C - Queue
- DSA using C - Parsing Expressions
- DSA using C - Stack
- DSA using C - Circular Linked List
- DSA using C - Doubly Linked List
- DSA using C - Linked List
- DSA using C - Array
- DSA using C - Concepts
- DSA using C - Algorithms
- DSA using C - Environment
- DSA using C - Overview
- DSA using C - Home
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
DSA using C - Algorithms
DSA using C - Algorithms
Algorithm
Algorithm is a step by step procedure, which defines a set of instructions to be executed in certain order to get the desired output. In term of data structures, following are the categories of algorithms.
Search − Algorithms to search an item in a datastrucure.
Sort − Algorithms to sort items in certain order
Insert − Algorithm to insert item in a datastructure
Update − Algorithm to update an existing item in a data structure
Delete − Algorithm to delete an existing item from a data structure
Algorithm analysis
Algorithm analysis deals with the execution time or running time of various operations of a data structure. Running time of an operation can be defined as no. of computer instructions executed per operation. As exact running time of any operation varies from one computer to another computer, we usually analyze the running time of any operation as some function of n, where n is the no. of items processed in that operation in a datastructure.
Asymptotic analysis
Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. For example, running time of one operation is computed as f(n) and of another operation as g(n2). Which means first operation running time will increase pnearly with the increase in n and running time of second operation will increase exponentially when n increases. Similarly the running time of both operations will be nearly same if n is significantly small.
Asymptotic Notations
Following are commonly used asymptotic notations used in calculating running time complexity of an algorithm.
Ο Notation
Ω Notation
θ Notation
Big Oh Notation, Ο
The Ο(n) is the formal way to express the upper bound of an algorithm s running time. It measures the worst case time complexity or longest amount of time an algorithm can possibly take to complete.
For example, for a function f(n)
Big Oh notation is used to simppfy functions. For example, we can replace a specific functional equation 7nlogn + n - 1 with Ο(f(nlogn)). Consider the scenario as follows −
It demonstrates that f(n) = 7nlogn +n - 1 is within the range of outout of O(nlogn) using constants c = 8 and n0 = 2.
Omega Notation, Ω
The Ω(n) is the formal way to express the lower bound of an algorithm s running time. It measures the best case time complexity or best amount of time an algorithm can possibly take to complete.
For example, for a function f(n)
Theta Notation, θ
The θ(n) is the formal way to express both the lower bound and upper bound of an algorithm s running time. It is represented as following.