Semester-2

Data Structures Using C

Course Code OMCA274

ISBN: 978-81-984510-2-1

Module-01
Introduction

OL15111
Master of Computer Application
 Module 01: Introduction

Internal Advisory Board (Self - Learning Material)

Chancellor, Sharda University and Mr. Pradeep Kumar Gupta
Chairman, SGI
Pro-Chancellor, Sharda University and Mr. Yatendra Kumar Gupta
Vice Chairman, SGI
Chief Executive Officer(CEO), Sharda Group Mr. Prashant Gupta
Vice-Chancellor Prof. (Dr.) Sibaram Khara
Pro Vice-Chancellor, Prof. (Dr.) Parma Nand
Dean, Sharda School of Engineering and
Technology
Registrar Dr. Vivek Kumar Gupta
Dean, Sharda School of Business Studies Prof. (Dr.) Sally Lukose
Dean, Sharda School of Humanities & Prof. (Dr.) Anviti Gupta
Social Sciences
Director, Centre For Distance and Online Prof. (Dr) Raju Ganesh Sunder
Education

Author Ms. Shreyi Mittal

Reviewer Ms. Tanaya Singh

Centre for Distance & Online Education, Sharda University Page|2

Data Structures Using C

Table of Contents
Module1: Unit 1 ................................................................................................................................................................. 4
Unit-1: Data Structure – Definition, Operations, Abstract Data Types ....................................................... 4
Topic 1: Data Structure and Structured Types, Data Types ....................................................................... 4
Topic 2: Abstract Data Types (ADTs) .................................................................................................................. 9
Topic 3: Differences Among Abstract Data Types (ADTs), Data Structures, and Structured
Types.............................................................................................................................................................................. 14
Topic 4: Introduction to Linear and Non-Linear Data Structures ........................................................ 18
Topic 5: Primitive and Non-Primitive Data Structures ............................................................................. 22
Module1: Unit 2 .............................................................................................................................................................. 26
Unit-2: Algorithms – Definition, Complexity ...................................................................................................... 26
Topic 6: Introduction to Algorithms: Understanding Need and Working ........................................ 26
Topic 7: Understanding Algorithm Efficiency: Memory Usage vs Speed in Algorithms ............. 30
Module1: Unit 3 .............................................................................................................................................................. 35
Unit-3: Asymptotic Notations ................................................................................................................................... 35
Topic 8: Introduction to Complexity: Time-Space Trade-Off ................................................................. 35
Topic 9: Asymptotic Notation .............................................................................................................................. 39
Topic 10: Upper Bound and Lower Bound with Respect to Algorithms............................................ 42
Check Your Knowledge ............................................................................................................................................... 46
Multiple Choice Questions (MCQs) .................................................................................................................... 47

Centre for Distance & Online Education, Sharda University Page|3

 Module 01: Introduction

Module 1: Unit 1
Unit-1: Data Structure – Definition, Operations, Abstract Data Types

Module1: Unit 1
Topic 1: Data Structure and Structured Types, Data Types
c
Introduction to Data Structures

A data structure is a way of organizing, managing, and storing data efficiently for

access and modification. It defines how data is arranged in memory and how

operations are performed on it. Data structures are crucial in computer science

for solving complex problems effectively and efficiently. They can be broadly

categorized as linear and non-linear structures, static and dynamic structures, or

hierarchical and networked structures.

Importance of Data Structures

1. Efficiency: Optimized storage and access mechanisms.

2. Reusability: Common structures can be reused in multiple applications.

3. Scalability: Handle increasing amounts of data without performance

degradation.

4. Organization: Improve readability and maintainability of code.

5. Problem Solving: Foundation for algorithms to solve problems in various

domains.

Categories of Data Structures

1. Linear Data Structures:

- Arrays

- Linked Lists

- Stacks

- Queues

Centre for Distance & Online Education, Sharda University Page|4

Data Structures Using C

2. Non-Linear Data Structures:

- Trees

- Graphs

- Heaps

3. Dynamic Data Structures:

- Resizable structures like dynamic arrays and linked lists.

4. Static Data Structures:

- Fixed-size arrays or other pre-allocated memory structures.

Structured Data Types

Structured types are aggregates of simpler data types, enabling more complex

and meaningful data representation. These are essential for representing

objects and relationships in programming.

Examples of Structured Types

1. Arrays:

- Fixed-size collections of elements of the same type.

- Accessed using indices.

- Example:

```c

int arr[5] = {1, 2, 3, 4, 5};

```

2. Records (Structures):

- Group different types of data under one name.

- Example in C:

```c

struct Student {

Centre for Distance & Online Education, Sharda University Page|5

 Module 01: Introduction

int rollNumber;

char name[50];

float marks;

};

```

3. Classes (Object-Oriented Programming):

- Encapsulate data and functions into objects.

- Example in Python:

```python

class Student:

def __init__(self, roll_number, name, marks):

self.roll_number = roll_number

[Link] = name

[Link] = marks

```

4. Unions:

- Special structures where all members share the same memory.

- Example:

```c

union Data {

int i;

float f;

};

```

5. Enumerations (Enums):

Centre for Distance & Online Education, Sharda University Page|6

Data Structures Using C

- Define a variable that can take a predefined set of values.

- Example in C:

```c

enum Color {RED, GREEN, BLUE};

```

6. File Data Structures:

- Represent structured data stored in files, such as CSV or JSON.

Data Types

A data type defines the type of data a variable can hold, specifying the possible

values, operations, and memory requirements.

Primitive Data Types

1. Integer:

- Whole numbers.

- Examples: `int`, `short`, `long`.

2. Floating-Point:

- Real numbers with decimal points.

- Examples: `float`, `double`.

3. Character:

- Single character or ASCII value.

- Example: `char`.

4. Boolean:

- Logical values: `true` or `false`.

- Example: `bool`.

Non-Primitive Data Types

1. Array: Collection of elements of the same type.

2. String: Sequence of characters.

3. Pointers: Memory addresses pointing to variables or data.

Centre for Distance & Online Education, Sharda University Page|7

 Module 01: Introduction

4. User-Defined Types: Structures, classes, and enums.

Abstract Data Types (ADTs)

1. Definition: Logical description of data and its operations.

2. Examples: Stack, Queue, List, Set, Map

Difference Between Data Structures and Data Types

Aspect Data Structures Data Types

Definition Organizes and manages data Specifies the type of data

Examples Arrays, Trees, Graphs Integer, Float, String

Abstraction Implementation-specific Implementation-independent

Operations Depends on structure Basic operations

Conclusion

Data structures and data types are fundamental concepts in computer science.

Data structures define the organization, storage, and manipulation of data,

whereas data types define the kind of data a variable can hold. Both concepts

work together to enable efficient, reliable, and scalable software development.

Understanding their nuances is key to designing and implementing effective

algorithms and applications.

Centre for Distance & Online Education, Sharda University Page|8

Data Structures Using C

Topic 2: Abstract Data Types (ADTs)

Introduction to Abstract Data Types

An Abstract Data Type (ADT) is a mathematical model for a data structure that

defines a set of operations and the behavior of the data without specifying the

details of its implementation. ADTs provide a way to focus on what data

structures do rather than how they do it, enabling abstraction and modularity in

programming. This concept is fundamental in computer science and software

development, as it allows developers to design and use data structures without

worrying about their underlying implementation.

Characteristics of Abstract Data Types

1. Encapsulation: ADTs encapsulate data and its associated operations, hiding

implementation details from the user.

2. Interface: An ADT specifies what operations can be performed on the data and

their expected outcomes.

3. Implementation Independence: The implementation of an ADT can be

changed without altering its interface or behavior.

4. Modularity: ADTs promote modularity, making programs easier to

understand, debug, and maintain.

Components of Abstract Data Types

1. Data: The collection of values that the ADT operates upon.

2. Operations: The functions or methods provided by the ADT to manipulate the

data. These operations include:

- Accessor methods: Retrieve data without modifying it.

- Mutator methods: Modify the state of the data.

- Constructors: Initialize new instances of the ADT.

- Destructors: Clean up resources used by the ADT.

Examples of Abstract Data Types

Centre for Distance & Online Education, Sharda University Page|9

 Module 01: Introduction

1. List

- Insertion: Add elements to the list.

- Deletion: Remove elements from the list.

- Traversal: Access each element sequentially.

- Search: Find an element in the list.

- Update: Modify elements in the list.

2. Stack

- push(element): Add an element to the top of the stack.

- pop(): Remove and return the top element.

- peek(): Return the top element without removing it.

- isEmpty(): Check if the stack is empty.

3. Queue

- enqueue(element): Add an element to the end of the queue.

- dequeue(): Remove and return the front element.

- peek(): Return the front element without removing it.

- isEmpty(): Check if the queue is empty.

4. Deque (Double-Ended Queue)

- insertFront(element): Add an element to the front.

- insertRear(element): Add an element to the rear.

- deleteFront(): Remove and return the front element.

- deleteRear(): Remove and return the rear element.

5. Priority Queue

- enqueue(element, priority): Add an element with a specific priority.

- dequeue(): Remove and return the element with the highest priority.

Centre for Distance & Online Education, Sharda University Page|10

Data Structures Using C

6. Set

- add(element): Add an element to the set.

- remove(element): Remove an element from the set.

- contains(element): Check if an element is in the set.

- union(otherSet): Return a set containing all elements in either set.

- intersection(otherSet): Return a set containing elements common to both

sets.

- difference(otherSet): Return a set containing elements in one set but not the

other.

Advantages of Abstract Data Types

1. Ease of Use: ADTs provide a simplified interface, abstracting away

implementation details.

2. Reusability: ADTs can be reused across different projects and applications.

3. Maintainability: Code is easier to maintain and modify due to the clear

separation of interface and implementation.

4. Error Reduction: Encapsulation reduces the likelihood of errors caused by

unintended interactions with the internal data.

Implementation of ADTs

ADTs can be implemented using various data structures such as arrays, linked

lists, or trees. For example:

- A List can be implemented using arrays or linked lists.

- A Stack can be implemented using arrays or linked lists, with operations

constrained to one end.

- A Queue can be implemented using arrays, linked lists, or circular buffers.

- A Priority Queue can be implemented using heaps.

Example: Stack Implementation in C

#include <stdio.h>

Centre for Distance & Online Education, Sharda University Page|11

 Module 01: Introduction

#include <stdlib.h>

#define MAX 100

typedef struct {

int items[MAX];

int top;

} Stack;

void initStack(Stack *s) {

s->top = -1;

int isFull(Stack *s) {

return s->top == MAX - 1;

int isEmpty(Stack *s) {

return s->top == -1;

void push(Stack *s, int value) {

if (isFull(s)) {

printf("Stack Overflow\n");

return;

s->items[++s->top] = value;

Centre for Distance & Online Education, Sharda University Page|12

Data Structures Using C

int pop(Stack *s) {

if (isEmpty(s)) {

printf("Stack Underflow\n");

return -1;

return s->items[s->top--];

int peek(Stack *s) {

if (isEmpty(s)) {

printf("Stack is Empty\n");

return -1;

return s->items[s->top];

int main() {

Stack stack;

initStack(&stack);

push(&stack, 10);

push(&stack, 20);

push(&stack, 30);

printf("Top element: %d\n", peek(&stack));

printf("Popped element: %d\n", pop(&stack));

printf("Popped element: %d\n", pop(&stack));

Centre for Distance & Online Education, Sharda University Page|13

 Module 01: Introduction

return 0;

Conclusion

Abstract Data Types play a crucial role in the design and implementation of

efficient and modular software. By focusing on the behavior and operations of

data structures, ADTs enable developers to build robust and reusable codebases.

They are a cornerstone of data structure theory and practice, forming the

foundation for more advanced concepts and applications in computer science.

Topic 3: Differences Among Abstract Data Types (ADTs), Data

Structures, and Structured Types

Introduction

Understanding the distinctions among Abstract Data Types (ADTs), Data

Structures, and Structured Types is crucial for designing efficient and scalable

software systems. While these concepts are interrelated, they differ in their levels

of abstraction, implementation, and use cases. This document provides a detailed

comparative table, complete with examples, syntax, and descriptions.

Comparative Table

Aspect Abstract Data Data Structures Structured Types

Types (ADTs)
Definition Logical model that Concrete Aggregates of
defines operations implementation of simpler data
and behaviors data that provides types to
without specifying a specific way of represent more
implementation. organizing and complex
manipulating data. relationships.
Abstraction High: Focuses on Medium: Focuses Medium to Low:
Level what operations on how data is Focuses on
are performed. organized and grouping
accessed. different types or
structures for
meaningful

Centre for Distance & Online Education, Sharda University Page|14

Data Structures Using C

representation.
Implementation Independent of Depends on the Implemented as
programming programming arrays, records,
language and language and classes, or
underlying chosen memory unions,
structure. model. depending on
language and
context.
Purpose Describes the Provides the Represents real-
functionality and mechanism for world entities by
interface for storing, accessing, combining
working with data. and managing multiple related
data. properties.
Examples Stack, Queue, Set, Linked List, Binary Arrays, Classes,
Map. Tree, Hash Table. Structs, Unions.
Syntax No direct syntax; Varies based on Explicit syntax for
implemented via the language and defining fields or
classes, methods, type of structure. elements of the
or interfaces. structured type.
Operations Push, Pop, Insert, Delete, Access fields,
Enqueue, Search, Traverse, modify values,
Dequeue, Union, Sort. iterate through
Intersection, etc. elements.
Programming Abstract: Defined Concrete: Semi-Concrete:
Dependency conceptually, not Dependent on the Implemented
bound to specific language and its with predefined
implementations. features. syntax for
structured
constructs.
Reusability High: Same ADT Medium: Medium:
can be reused Implementation- Depends on the
across different specific, but extent to which
implementations. adaptable to structured types
various problems. are generalized
or specialized.
Flexibility High: Can be Medium: Bound Low to Medium:
implemented in by the structure’s Typically rigid
multiple ways (e.g., defined due to explicit
Stack via Array or constraints. type definitions.
Linked List).

Centre for Distance & Online Education, Sharda University Page|15

 Module 01: Introduction

Detailed Examples and Syntax

Data Structure: Linked List
Definition: A linear data structure consisting of nodes, where each node contains
a data field and a reference to the next node.
Example in C:

Centre for Distance & Online Education, Sharda University Page|16

Data Structures Using C

Structured Type: Struct in C

Definition: A structure (or struct) in C aggregates different types of data into a
single logical unit.
Example in C:

Conclusion

Abstract Data Types, Data Structures, and Structured Types each serve unique

roles in computer science. ADTs emphasize the "what" of data manipulation, Data

Structures focus on the "how," and Structured Types bring context and real-world

relevance. Understanding their distinctions enables developers to choose the

right tools for efficient problem-solving.

Centre for Distance & Online Education, Sharda University Page|17

 Module 01: Introduction

Topic 4: Introduction to Linear and Non-Linear Data Structures

What are Data Structures?

- A data structure is a specialized format for organizing, managing, and storing
data in a way that it can be efficiently accessed and modified.
- Data structures are broadly classified into:
- Linear Data Structures
- Non-Linear Data Structures

Key Differences Between Linear and Non-Linear Data Structures:

Feature Linear Data Structures Non-Linear Data

Structures

Structure Sequential and ordered Hierarchical or graph-like

Traversal Single level Multiple levels

Memory Requires more memory Efficient memory usage

Utilization

Complexity Easier to implement Complex in nature

Examples Arrays, Linked Lists, Stacks, Trees, Graphs

Queues

Linear Data Structures

Characteristics
- Elements are arranged sequentially in a line.
- Each element has a single successor and a single predecessor, except the first
and last elements.
- Easier to implement and understand.

Types of Linear Data Structures

----------------------------------
1. Array
- Definition: A collection of elements identified by an index.
- Properties:
- Fixed size.
- Homogeneous elements.
- Applications: Used in mathematical computations, data storage.

Centre for Distance & Online Education, Sharda University Page|18

Data Structures Using C

- Example in C:

2. Linked List
- Definition: A dynamic collection of nodes, where each node contains data and
a pointer to the next node.
- Properties:
- Dynamic size.
- Efficient insertion and deletion.
- Applications: Used in memory management, implementation of stacks and
queues.
- Example Types: Singly, Doubly, Circular.

3. Stack
- Definition: A collection of elements that follows the LIFO (Last In, First Out)
principle.
- Applications: Function call management, undo operations.
- Example in C:

4. Queue
- Definition: A collection of elements that follows the FIFO (First In, First Out)
principle.
- Applications: Task scheduling, buffering.
- Variants: Circular Queue, Priority Queue, Deque.
Non-Linear Data Structures
Characteristics
- Elements are arranged in a hierarchical manner.
- Each element can be connected to multiple elements.
- More complex relationships between data elements.

Types of Non-Linear Data Structures

-------------------------------------

Centre for Distance & Online Education, Sharda University Page|19

 Module 01: Introduction

1. Tree
- Definition: A hierarchical structure consisting of nodes, with one node as the
root and zero or more child nodes.
- Types:
- Binary Tree, Binary Search Tree (BST), AVL Tree, B-Tree.
- Applications: File systems, databases, AI algorithms.
- Example in C:

2. Graph
- Definition: A collection of nodes (vertices) connected by edges.
- Types:
- Directed Graph (Digraph), Undirected Graph, Weighted Graph.
- Applications: Social networks, routing algorithms, modeling real-world
systems.
- Example in C:

Comparison
Advantages of Linear Data Structures
--------------------------------------
1. Ease of Implementation: Simpler to implement due to sequential organization.
2. Efficient Traversal: Can traverse elements in a straightforward manner.
3. Memory Utilization: Works well with a fixed memory allocation.

Advantages of Non-Linear Data Structures

-----------------------------------------

Centre for Distance & Online Education, Sharda University Page|20

Data Structures Using C

1. Complex Relationships: Can represent real-world hierarchical or network

relationships.
2. Efficient Operations: Faster for operations like search and insert in balanced
trees.
3. Dynamic: Adapts well to varying sizes and structures.

Key Use Cases

Use Case Preferred Data Structure

Sequential data access Arrays, Linked Lists

Backtracking or recursion Stack

Priority-based task execution Priority Queue

Hierarchical data Tree

Network analysis Graph

Applications and Examples

Applications of Linear Data Structures
---------------------------------------
1. Arrays:
- Used in storing data in tabular forms, such as matrices.
- Examples: Game boards, image data storage.
2. Stacks:
- Undo functionality in text editors.
- Expression evaluation (e.g., converting infix to postfix).
3. Queues:
- Print spooling in operating systems.
- Real-time scheduling.

Applications of Non-Linear Data Structures

------------------------------------------
1. Trees:
- Parsing expressions in compilers.
- Implementing database indexes (e.g., B-Trees in SQL).
2. Graphs:
- Modeling networks like roads, telecom, or social connections.
- Algorithms like Dijkstra’s shortest path, Prim’s, and Kruskal’s.

Centre for Distance & Online Education, Sharda University Page|21

 Module 01: Introduction

Topic 5: Primitive and Non-Primitive Data Structures

Introduction
Data structures are the frameworks for organizing, managing, and storing data
efficiently. They are pivotal in ensuring optimized data access and manipulation,
which is essential in software development, algorithm design, and systems
programming.

Categories of Data Structures

Data structures are broadly classified into:
1. Primitive Data Structures
- Represent basic data types.
- Directly supported by most programming languages.
2. Non-Primitive Data Structures
- Derived from primitive data types.
- Enable advanced operations and data handling.
The choice of data structure directly impacts:
- Memory usage.
- Algorithm efficiency.
- Program maintainability.
Primitive Data Structures
Primitive data structures are the simplest forms of data storage, designed to
hold a single value. They come pre-defined in most programming languages.
Types of Primitive Data Structures
1. Integer (int): Stores whole numbers.
- Examples: Age, counter, loop variable.
- Operations: Addition, subtraction, modulus, etc.
Example (C Code):

2. Float (decimal): Stores fractional or decimal values.

- Examples: Prices, scientific calculations.
- Operations: Arithmetic operations, rounding, etc.

Example (C Code):

Centre for Distance & Online Education, Sharda University Page|22

Data Structures Using C

3. Character (char): Holds single characters, often represented using ASCII

values.
- Examples: Initials, symbols.

Example (C Code):

4. Boolean: Represents true/false or yes/no values.

- Examples: Conditions, switches.

Example (C Code):

Non-Primitive Data Structures

Non-primitive data structures are more sophisticated structures capable of
holding multiple values. They are derived using primitive types and provide
efficient ways to store, access, and manipulate data.

Types of Non-Primitive Data Structures

1. Linear Data Structures:
- Data elements are stored sequentially.
- Examples: Arrays, Stacks, Queues, Linked Lists.
Example for Arrays (C Code):
int marks[5] = {78, 85, 92, 68, 74};
2. Non-Linear Data Structures:
- Data is organized hierarchically or as a network.
- Examples: Trees, Graphs.

Example for Trees (Hierarchical Representation):

Centre for Distance & Online Education, Sharda University Page|23

 Module 01: Introduction

Root
├── Child1
└── Child2
├── Grandchild1
└── Grandchild2
Comparison Between Primitive and Non-Primitive Data Structures
Aspect Primitive Data Structures Non-Primitive Data Structures
Definition Basic, single-value data storage Advanced, multi-value data
storage
Structure Pre-defined by programming User-defined and derived
languages
Examples int, float, char, boolean Arrays, Trees, Graphs
Flexibility Rigid Highly flexible
Usage Simple operations like Advanced algorithms and
calculations applications

Practical Applications

1. Applications of Primitive Data Structures:

- Integer: Used in counting, loops, indexing.

- Float: Essential for scientific computations, graphics.

- Character: Text processing, file names.

- Boolean: Conditional statements, toggling options.

2. Applications of Non-Primitive Data Structures:

- Arrays: Store fixed-size datasets like temperature logs.

- Stacks: Undo-redo operations in editors.

- Queues: Process scheduling, customer service systems.

- Trees: File systems, parsing expressions.

- Graphs: Represent social networks, roadmaps.

Centre for Distance & Online Education, Sharda University Page|24

Data Structures Using C

Conclusion

Understanding the distinctions between primitive and non-primitive data

structures enables developers to choose the right tools for efficient data

handling. Primitive types form the foundation, while non-primitive structures

provide advanced capabilities to solve complex computational problems.

Centre for Distance & Online Education, Sharda University Page|25

 Module 01: Introduction

Module 1: Unit 2

Unit-2: Algorithms – Definition, Complexity

Module1: Unit 1
c
Topic 6: Introduction to Algorithms: Understanding Need and

Working

Introduction

An algorithm is a well-defined step-by-step procedure or set of rules to solve a

specific problem or perform a computation. Algorithms are the backbone of

computer science and play a crucial role in programming and software

development.

Key Characteristics of Algorithms

1. Input: Accepts zero or more inputs.

2. Output: Produces at least one output.

3. Definiteness: Each step is clearly defined.

4. Finiteness: It terminates after a finite number of steps.

5. Effectiveness: Every operation is basic enough to be carried out manually if

needed.

Why Study Algorithms?

1. Efficiency: Optimize the use of resources (time and space).

2. Problem Solving: Provide structured solutions to complex problems.

3. Foundational Knowledge: Basis for learning advanced topics in computer

science such as data structures, machine learning, and artificial intelligence.

Applications of Algorithms

Centre for Distance & Online Education, Sharda University Page|26

Data Structures Using C

- Searching (e.g., binary search).

- Sorting (e.g., quicksort, mergesort).

- Networking (e.g., Dijkstra's algorithm for shortest path).

- Cryptography (e.g., RSA algorithm).

Why Do We Need Algorithms?

1. Problem Solving: Algorithms provide a systematic approach to solve problems.

2. Optimization: Minimizing the use of resources like memory, computation time,

or energy.

3. Scalability: Ensures solutions can handle large datasets or high user traffic

efficiently.

4. Automation: Automates repetitive tasks.

5. Real-World Applications: Algorithms are used in various industries such as

finance, healthcare, and logistics.

6. Competitive Programming: Essential for programming competitions and

technical interviews.

Example Problem:

- Task: Sort an array of numbers in ascending order.

- Algorithm: Bubble Sort (or any other sorting algorithm).

How Algorithms Work

1. Algorithm Design Process:

- Understand the Problem: Identify inputs and outputs, and analyze constraints.

- Choose a Strategy: Use techniques like divide and conquer, greedy algorithms,

or dynamic programming.

- Design the Algorithm: Write pseudocode or a high-level description.

- Implement in Code: Translate the algorithm into a programming language.

- Test and Optimize: Check for correctness and efficiency.

Centre for Distance & Online Education, Sharda University Page|27

 Module 01: Introduction

Example: Linear Search

- Problem: Find if a target number exists in a list.

- Steps:

1. Start from the first element.

2. Compare each element with the target.

3. Return the index if found, or indicate it's not in the list.

Pseudocode for Linear Search

Algorithm LinearSearch(array, target):

for each element in array:

if element == target:

return index

return -1

Measuring Algorithm Efficiency

Time Complexity

- Indicates how the execution time grows with input size.

- Common classifications:

- O(1): Constant time.

- O(log n): Logarithmic time.

- O(n): Linear time.

- O(n^2): Quadratic time.

Space Complexity

- Indicates the amount of memory required.

- Factors to consider:

- Input size.

- Temporary variables.

Example: Comparing Sorting Algorithms

Centre for Distance & Online Education, Sharda University Page|28

Data Structures Using C

- Bubble Sort:

- Time Complexity: O(n^2)

- Space Complexity: O(1)

- Merge Sort:

- Time Complexity: O(n log n)

- Space Complexity: O(n)

Types of Algorithms and Their Use Cases

1. Brute Force:

- Exhaustive search for all possibilities.

- Example: Finding all subsets of a set.

2. Divide and Conquer:

- Breaks the problem into smaller sub-problems.

- Example: Merge Sort.

3. Greedy Algorithms:

- Makes locally optimal choices at each step.

- Example: Dijkstra’s algorithm.

4. Dynamic Programming:

- Solves overlapping sub-problems by storing solutions.

- Example: Fibonacci sequence calculation.

5. Backtracking:

- Explores all possibilities and backtracks on invalid paths.

- Example: Solving a maze.

Real-World Examples

Centre for Distance & Online Education, Sharda University Page|29

 Module 01: Introduction

- Sorting Algorithms: Organizing data in e-commerce.

- Graph Algorithms: Optimizing road networks.

- String Matching Algorithms: DNA sequencing.

Conclusion

Algorithms are fundamental to computer science, providing structured solutions

to complex problems. Understanding their need, design, and working principles

helps in creating efficient software solutions across industries. Mastery of

algorithms is essential for anyone pursuing a career in technology.

Topic 7: Understanding Algorithm Efficiency: Memory Usage vs Speed

in Algorithms

Introduction

Algorithm efficiency is a crucial concept in computer science, influencing the

design and implementation of software systems. Efficient algorithms optimize

the use of resources, such as time (speed) and space (memory). Striking a

balance between these two factors is essential for practical applications, as

resource constraints vary across systems and use cases. This document delves

into the importance of algorithm efficiency, key factors affecting it, and

strategies to optimize memory usage and speed.

Factors Influencing Algorithm Efficiency

Time Complexity (Speed)

Time complexity measures the amount of time an algorithm takes to complete

as a function of the input size (n). It is expressed using Big-O notation, which

provides an upper bound for the growth rate of the running time. Common time

complexities include:

- O(1): Constant time, irrespective of input size.

- O(log n): Logarithmic time, e.g., binary search.

Centre for Distance & Online Education, Sharda University Page|30

Data Structures Using C

- O(n): Linear time, e.g., iterating over an array.

- O(n^2): Quadratic time, e.g., nested loops.

Time complexity impacts the speed of algorithms, especially for large input sizes.

Space Complexity (Memory Usage)

Space complexity measures the amount of memory an algorithm uses during

execution. It consists of:

- Fixed Part: Memory for constants, instructions, and fixed variables.

- Variable Part: Memory for dynamic allocation, including input, output, and

temporary data structures.

Like time complexity, space complexity is expressed using Big-O notation.

Trade-Offs Between Memory and Speed

Memory-Intensive Algorithms

Algorithms optimized for speed often consume more memory. For example,

caching intermediate results (as in dynamic programming) reduces computation

time but increases memory usage. Examples include:

- Fibonacci Sequence: Using memoization significantly reduces time complexity

from O(2^n) to O(n), but requires additional memory.

- Sorting Algorithms: Merge sort uses O(n log n) time but O(n) space, whereas

quicksort uses O(n log n) time with O(log n) space.

Time-Intensive Algorithms

Memory-efficient algorithms may require more computational time. For

instance, recalculating results instead of storing them reduces memory usage

but increases execution time. Examples include:

- Recursive Algorithms: Without memoization, they save memory but repeat

calculations, increasing runtime.

Centre for Distance & Online Education, Sharda University Page|31

 Module 01: Introduction

- In-Place Sorting: Bubble sort uses O(1) extra space but has O(n^2) time

complexity.

Measuring Algorithm Efficiency

Profiling Tools

Developers use profiling tools to analyze the runtime and memory usage of

algorithms. Popular tools include:

- Valgrind: Detects memory leaks and analyzes memory usage.

- gprof: Profiles the execution time of functions.

- Big-O Cheat Sheet: Provides reference time and space complexities for

common algorithms.

Benchmarking

Benchmarking involves running algorithms with various input sizes to measure

performance. Metrics include:

- Execution Time: Average, worst-case, and best-case times.

- Peak Memory Usage: Maximum memory consumed during execution.

Strategies for Optimization

Reducing Time Complexity

- Divide and Conquer: Break problems into smaller sub-problems, solve them,

and combine results. Examples: Merge Sort, Quick Sort.

- Dynamic Programming: Cache results of sub-problems to avoid redundant

calculations. Example: Longest Common Subsequence.

- Greedy Algorithms: Make locally optimal choices to find a global solution.

Example: Dijkstra’s Algorithm.

Reducing Space Complexity

- In-Place Algorithms: Modify input data instead of using additional data

structures. Example: In-place reversal of a linked list.

Centre for Distance & Online Education, Sharda University Page|32

Data Structures Using C

- Iterative Approaches: Replace recursion with iteration to save stack memory.

- Bit Manipulation: Use bits to store and process data compactly. Example:

Checking if a number is a power of two.

Case Studies

Case Study: Matrix Multiplication

Consider two methods for multiplying matrices:

1. Naïve Method:

- Time Complexity: O(n^3)

- Space Complexity: O(n^2) for the result matrix.

- Suitable for small matrices.

2. Strassen’s Algorithm:

- Time Complexity: O(n^{2.81})

- Space Complexity: Higher due to recursive calls and additional matrices.

- Suitable for larger matrices where speed is critical.

Case Study: Graph Traversal

1. Breadth-First Search (BFS):

- Time Complexity: O(V + E), where V is vertices and E is edges.

- Space Complexity: O(V) for queue storage.

2. Depth-First Search (DFS):

- Time Complexity: O(V + E).

- Space Complexity: O(h), where h is the height of the recursion stack.

- DFS uses less memory but is prone to stack overflow for deep graphs.

Conclusion

Understanding and balancing memory usage and speed are critical for designing

efficient algorithms. While optimization often requires trade-offs, the choice

Centre for Distance & Online Education, Sharda University Page|33

 Module 01: Introduction

depends on specific application requirements and system constraints. Profiling

and benchmarking are essential tools for evaluating and refining algorithm

performance. By applying advanced techniques and strategies, developers can

create algorithms that effectively balance time and space complexities.

Centre for Distance & Online Education, Sharda University Page|34

Data Structures Using C

Module 1: Unit 3

Unit-3: Asymptotic Notations

Module1: Unit 1
c
Topic 8: Introduction to Complexity: Time-Space Trade-Off

Introduction

The study of algorithmic complexity focuses on evaluating the efficiency of

algorithms in terms of resource consumption. The two critical resources are

time, referring to the duration an algorithm takes to execute, and space,

referring to the memory it occupies during execution. A time-space trade-off

occurs when optimizing one of these resources necessitates increased usage of

the other. This document explores the principles of time-space trade-offs,

examples, and practical considerations.

Understanding Time Complexity

Definition

Time complexity quantifies the amount of computational time an algorithm

requires to process an input of size n. It provides a theoretical framework to

compare algorithms' performance.

Big-O Notation

Big-O notation describes the upper bound of an algorithm's running time,

providing an asymptotic measure of its growth rate. Common complexities

include:

- O(1): Constant time.

- O(log n): Logarithmic time.

Centre for Distance & Online Education, Sharda University Page|35

 Module 01: Introduction

- O(n): Linear time.

- O(n^2): Quadratic time.

Understanding Space Complexity

Definition

Space complexity measures the memory an algorithm requires. It includes:

1. Fixed Part: Memory for constants and instructions.

2. Variable Part: Memory dependent on input size and algorithmic operations.

Memory Allocation

Space complexity evaluates:

- Temporary variables.

- Auxiliary data structures.

- Recursion stack.

Time-Space Trade-Off

Concept

In many scenarios, optimizing for speed increases memory usage, and vice

versa. The time-space trade-off arises because faster algorithms often rely on

precomputed data or additional data structures, while memory-efficient

algorithms recompute values to minimize storage.

Key Principles

1. Caching and Lookup Tables: Precomputing values (e.g., memoization) speeds

up execution but consumes memory.

2. Recursion vs. Iteration: Recursion saves code complexity but requires stack

memory, while iteration uses less memory but can be slower.

3. In-Place Algorithms: Reduce memory usage by modifying the input directly,

often at the cost of increased complexity or slower execution.

Centre for Distance & Online Education, Sharda University Page|36

Data Structures Using C

Examples of Time-Space Trade-Offs

Dynamic Programming

Example: Fibonacci Sequence

1. Recursive Approach:

- Time Complexity: O(2^n).

- Space Complexity: O(n) for the recursion stack.

2. Dynamic Programming with Memoization:

- Time Complexity: O(n).

- Space Complexity: O(n) for the lookup table.

3. Iterative Approach:

- Time Complexity: O(n).

- Space Complexity: O(1).

Sorting Algorithms

1. Merge Sort:

- Time Complexity: O(n log n).

- Space Complexity: O(n) due to auxiliary arrays.

2. Heap Sort:

- Time Complexity: O(n log n).

- Space Complexity: O(1).

3. Quick Sort:

- Time Complexity: O(n log n) (average case).

- Space Complexity: O(log n) for the recursion stack.

Practical Considerations

Hardware Constraints

- Memory-Constrained Systems: Optimize for space, even at the cost of slower

execution. Example: Embedded systems.

Centre for Distance & Online Education, Sharda University Page|37

 Module 01: Introduction

- High-Performance Systems: Optimize for time when memory is abundant.

Example: Data centers.

Application-Specific Requirements

- Real-Time Systems: Require low execution time, favoring speed over space.

- Big Data Applications: Require efficient memory management to handle large

datasets.

Optimization Techniques

- Lazy Evaluation: Compute values only when needed.

- Compression: Store data in compressed formats to save space.

- Parallel Processing: Distribute computations across multiple processors to

improve time efficiency.

Advanced Topics

Hybrid Approaches

Some algorithms balance time and space efficiency through adaptive methods.

Example: Timsort combines merge sort and insertion sort to optimize

performance.

Space-Time Complexity Analysis

Advanced profiling tools like Valgrind and gprof can analyze the trade-offs in

detail, helping developers make informed decisions.

Conclusion

The time-space trade-off is a fundamental consideration in algorithm design.

Understanding the principles and applying them effectively can lead to

optimized algorithms tailored to specific applications. While the choice often

depends on system constraints and requirements, striking a balance ensures

efficient and reliable software solutions.

Centre for Distance & Online Education, Sharda University Page|38

Data Structures Using C

Topic 9: Asymptotic Notation

Introduction

Asymptotic notation is a mathematical framework used to describe the efficiency

and behavior of algorithms as the input size grows infinitely large. It provides a

standardized way to express the time or space complexity of algorithms, allowing

comparisons independent of hardware or software implementations. This

document explains the core concepts, types, and applications of asymptotic

notation in analyzing algorithms.

Basics of Asymptotic Notation

Purpose

The primary goal of asymptotic notation is to:

- Simplify complexity expressions by focusing on dominant terms.

- Provide a machine-independent method to analyze algorithm performance.

- Abstract away constants and lower-order terms that have negligible impact for

large inputs.

Mathematical Foundation

Asymptotic analysis relies on functions that map input size \(n\) to time or space

usage. For example, if an algorithm takes \(f(n) = 3n^2 + 5n + 10\) steps:

- The dominant term is \(n^2\), which determines the growth rate for large \(n\).

- Constants and lower-order terms are ignored.

Types of Asymptotic Notation

Big-O Notation (O)

Big-O notation provides an upper bound on the growth rate of a function. It defines

the worst-case complexity, ensuring an algorithm never performs worse than the

stated bound.

Centre for Distance & Online Education, Sharda University Page|39

 Module 01: Introduction

Formal Definition:

Example:

2.2 Omega Notation (Ω)

Omega notation provides a lower bound on the growth rate of a function. It

defines the best-case complexity, ensuring an algorithm performs at least as well

as the stated bound.

Formal Definition:

Example:

2.3 Theta Notation (Θ)

Theta notation provides a tight bound on the growth rate of a function. It defines

the average-case complexity, ensuring the function grows asymptotically at the

same rate as the bound.

Formal Definition:

Example:

Centre for Distance & Online Education, Sharda University Page|40

Data Structures Using C

Applications in Algorithm Analysis

Comparing Algorithms

Asymptotic notation allows developers to compare algorithms by their efficiency:

- Linear Search: \(O(n)\)

- Binary Search: \(O(\log n)\)

- Merge Sort: \(O(n \log n)\)

- Bubble Sort: \(O(n^2)\)

Identifying Bottlenecks

By analyzing time and space complexity, bottlenecks can be identified and

addressed:

- Nested loops often lead to \(O(n^2)\) complexity.

- Recursive algorithms may require \(O(n)\) stack space.

Optimization

- Replace \(O(n^2)\) algorithms with \(O(n \log n)\) alternatives.

- Use data structures that reduce complexity, such as hash tables for \(O(1)\)

lookups.

Real-World Examples

Sorting Algorithms

- Merge Sort: \(O(n \log n)\) for divide-and-conquer strategy.

- Quick Sort: \(O(n^2)\) worst-case but \(O(n \log n)\) average-case.

Graph Algorithms

- Breadth-First Search (BFS): \(O(V + E)\), where \(V\) is vertices and \(E\) is edges.

- Dijkstra’s Algorithm: \(O(V^2)\) for dense graphs.

4.3 Searching Algorithms

Centre for Distance & Online Education, Sharda University Page|41

 Module 01: Introduction

- Linear Search: \(O(n)\) for unsorted arrays.

- Binary Search: \(O(\log n)\) for sorted arrays.

Conclusion

Asymptotic notation is an indispensable tool for algorithm analysis. It provides a

clear, mathematical way to express efficiency, enabling developers to evaluate,

compare, and optimize algorithms. By understanding the types and applications

of asymptotic notation, developers can make informed decisions and build

efficient, scalable systems.

Topic 10: Upper Bound and Lower Bound with Respect to Algorithms

Introduction

Understanding the efficiency of algorithms is a cornerstone of computer science.

Two essential concepts in this domain are upper bound and lower bound. These

terms help define the computational limits of algorithms by describing their

performance and efficiency across different scenarios. Upper bounds define the

maximum resources required, while lower bounds establish the minimum. This

document explores these concepts, their mathematical formulations, and their

significance in algorithm analysis.

What is an Upper Bound?

Definition

An upper bound of an algorithm refers to a function that represents the worst-

case performance. It is a guarantee that the algorithm will not exceed a certain

amount of time or space, regardless of the input.

Big-O Notation

Upper bounds are commonly expressed using Big-O notation, which describes the

asymptotic upper limit of an algorithm's growth rate.

Centre for Distance & Online Education, Sharda University Page|42

Data Structures Using C

Formal Definition:

f(n) ∈ O(g(n)) iff ∃ c > 0, n₀ > 0 such that f(n) ≤ c ⋅ g(n) for all n ≥ n₀.

Example:

Consider the time complexity f(n) = 3n² + 5n + 10:

- Dominant term: n²

- Upper bound: O(n²)

The constant factors and lower-order terms are ignored in Big-O notation, as

they are negligible for large n.

Applications

- Worst-case Analysis: Ensures algorithms handle the largest or most complex

inputs efficiently.

- Algorithm Comparison: Provides a standard framework to compare different

algorithms.

Common Misconceptions

- Big-O does not indicate the exact runtime; it shows the upper limit for growth.

- The actual execution time may be lower than the upper bound for specific

inputs.

What is a Lower Bound?

Definition

A lower bound of an algorithm refers to a function that represents the best-case

performance. It guarantees that the algorithm will take at least a certain amount

of time or space for any input.

Omega Notation

Lower bounds are expressed using Omega notation, which describes the

asymptotic lower limit of an algorithm's growth rate.

Centre for Distance & Online Education, Sharda University Page|43

 Module 01: Introduction

Formal Definition:

f(n) ∈ Ω(g(n)) iff ∃ c > 0, n₀ > 0 such that f(n) ≥ c ⋅ g(n) for all n ≥ n₀.

Example:

Consider the time complexity f(n) = 3n² + 5n + 10:

- Dominant term: n²

- Lower bound: Ω(n²)

The lower bound provides a guarantee that the algorithm will not perform faster

than a given rate.

Applications

- Best-case Analysis: Useful for identifying the minimum resources an algorithm

will use.

- Theoretical Limits: Helps establish what is fundamentally possible with a given

problem.

Common Misconceptions

- Omega does not indicate the exact runtime; it shows the lower limit for growth.

- An algorithm may perform worse than the lower bound for certain inputs.

Tight Bounds

Theta Notation

When the upper and lower bounds of an algorithm match, they form a tight

bound, expressed using Theta notation (Θ).

Formal Definition:

f(n) ∈ Θ(g(n)) iff ∃ c₁, c₂ > 0, n₀ > 0 such that c₁ ⋅ g(n) ≤ f(n) ≤ c₂ ⋅ g(n) for all n ≥ n₀.

Example:

For f(n) = 3n² + 5n + 10:

Centre for Distance & Online Education, Sharda University Page|44

Data Structures Using C

- Upper Bound: O(n²)

- Lower Bound: Ω(n²)

- Tight Bound: Θ(n²)

Importance of Tight Bounds

- Tight bounds provide precise growth rates, helping identify the actual efficiency

of an algorithm.

- They are crucial for selecting the optimal algorithm for a specific use case.

Conclusion

Upper and lower bounds are fundamental in understanding the efficiency and

limitations of algorithms. By analyzing these bounds, developers can evaluate

worst-case and best-case scenarios, optimize performance, and address

computational challenges. Together, upper and lower bounds provide a

comprehensive picture of an algorithm’s behavior, enabling the design of efficient,

scalable solutions.

Centre for Distance & Online Education, Sharda University Page|45

 Module 01: Introduction

Check Your Knowledge

Short Questions

1. Define a data structure and list two types of linear data structures.

2. What is an algorithm? Mention the key characteristics of a good algorithm.

3. Explain the need for asymptotic notations in algorithm analysis.

4. What is the difference between time complexity and space complexity?

5. Give the formal definition of Big-O notation.

6. How is Big-Omega notation different from Big-O notation?

7. Define Theta-notation and its significance in evaluating algorithms.

8. What are primitive and non-primitive data structures?

9. State the advantages of analyzing algorithms using asymptotic notations.

10. Write the general structure of an algorithm in pseudocode.

Long Questions

1. Explain the classification of data structures with examples. How do linear and
non-linear data structures differ?

2. Describe the various asymptotic notations with formal definitions and

graphical interpretations.

3. Why is it important to consider the time complexity of an algorithm? Illustrate

with examples.

4. Compare and contrast the best-case, worst-case, and average-case

complexities of an algorithm using linear search as an example.

5. Write an algorithm to search an element in an array and analyze its time

complexity.

Centre for Distance & Online Education, Sharda University Page|46

Data Structures Using C

6. Discuss the role of space complexity in algorithm analysis. Provide examples

where space optimization is critical.

7. How would you evaluate an algorithm’s efficiency when the input size grows?
Explain with relevant examples.

8. Describe with an example how Big-O notation can be used to prove the
efficiency of a sorting algorithm.

9. Illustrate how asymptotic notations help in comparing two sorting algorithms

theoretically.

Multiple Choice Questions (MCQs)

1. Which of the following is a non-linear data structure?

a) Stack

b) Queue

c) Tree

d) Array

2. What does Big-O notation represent?

a) Lower bound of an algorithm

b) Exact complexity

c) Upper bound of an algorithm

d) Average time

3. Which of the following is NOT a characteristic of an algorithm?

a) Ambiguity

b) Finiteness

Centre for Distance & Online Education, Sharda University Page|47

 Module 01: Introduction

c) Input

d) Output

4. Which of the following notations provides a tight bound on an algorithm’s

growth rate?

a) Big O

b) Big-Omega

c) Big-Theta

d) Small o

5. Which data structure uses LIFO (Last In First Out) principle?

a) Queue

b) Array

c) Stack

d) Linked List

6. Which of the following is used to allocate memory dynamically?

a) malloc()

b) static

c) define

d) int

Centre for Distance & Online Education, Sharda University Page|48

Data Structures Using C

7. What does time complexity measure?

a) The amount of memory used

b) The execution time as a function of input size

c) The programming effort required

d) The debugging difficulty

8. Which of the following is not typically considered in space complexity?

a) Input variables

b) Output space

c) Auxiliary variables

d) CPU speed

9. Which data structure is suitable for implementing recursion?

a) Queue

b) Stack

c) Linked List

d) Tree

Centre for Distance & Online Education, Sharda University Page|49

 Module 01: Introduction

Answers for Multiple Choice questions:

[Link] Answers
1 c) Tree
2 c) Upper bound of an algorithm
3 a) Ambiguity
4 c) Big-Theta
5 c) Stack
6 a) malloc()
7 b) The execution time as a function of input size
8 d) CPU speed
9 b) Stack

Centre for Distance & Online Education, Sharda University Page|50

Data Structures Using C

Centre for Distance & Online Education, Sharda University Page|51