KEMBAR78
DSA (Unit-1) Future Minds - Short Notes | PDF | Time Complexity | Theoretical Computer Science
Scribd
Upload
10 views2 pages

DSA (Unit-1) Future Minds - Short Notes

The document provides an overview of data structures, including definitions of data, information, records, and files. It covers elementary data organizations, operations on data structures, algorithm analysis, asymptotic notations, time-space trade-offs, and searching techniques such as linear and binary search. Key concepts include time and space complexity, with examples illustrating their application.

Uploaded by

kingkohli2024raja
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views2 pages

DSA (Unit-1) Future Minds - Short Notes

The document provides an overview of data structures, including definitions of data, information, records, and files. It covers elementary data organizations, operations on data structures, algorithm analysis, asymptotic notations, time-space trade-offs, and searching techniques such as linear and binary search. Key concepts include time and space complexity, with examples illustrating their application.

Uploaded by

kingkohli2024raja
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

DSA (UNIT – 1)

1. Introduction & Basic Terminologies

 Data – Raw facts and figures without any meaning (e.g., 10, 20, "Apple").

 Information – Processed data that has meaning.

 Data Item – A single unit of value (e.g., a student's roll number).

 Record – A collection of related data items (e.g., roll number, name, marks of a student).

 File – A collection of related records.

2. Elementary Data Organizations

 Linear Organization – Data elements are arranged sequentially (e.g., Arrays, Linked Lists).

 Non-Linear Organization – Data elements are arranged hierarchically (e.g., Trees, Graphs).

 Primitive Data Structures – Integers, floats, characters, pointers, etc.

 Non-Primitive Data Structures –

o Linear: Arrays, Linked Lists, Stacks, Queues

o Non-Linear: Trees, Graphs

3. Data Structure Operations

 Insertion – Adding an element to the structure.

 Deletion – Removing an element.

 Traversal – Visiting each element at least once.

 Searching – Finding the location of an element.

 Sorting – Arranging elements in a specific order.

 Updation – Modifying an existing element.

4. Analysis of an Algorithm

 Algorithm – A finite step-by-step procedure to solve a problem.

 Analysis helps in evaluating efficiency based on:

1. Time Complexity – Time taken to execute.

2. Space Complexity – Memory used during execution.


5. Asymptotic Notations

Used to describe time complexity growth as input size n increases:

 Big O (O) – Upper bound (worst case).

 Big Omega (Ω) – Lower bound (best case).

 Big Theta (Θ) – Tight bound (average case).

Example:
For a loop for(i=0;i<n;i++), time complexity = O(n).

6. Time-Space Trade-Off

 Less Space → More Time (e.g., recomputing values instead of storing them).
 More Space → Less Time (e.g., using extra memory to store precomputed results like hash
tables).

7. Searching Techniques

A. Linear Search

 Algorithm: Check each element sequentially.

 Time Complexity:

o Best Case → O(1) (element found at first position)

o Worst Case → O(n) (element not found or at last position)

 Space Complexity: O(1)

B. Binary Search

 Works only on sorted arrays.

 Algorithm:

1. Find the middle element.

2. If key = middle → found.

3. If key < middle → search left half.

4. If key > middle → search right half.

 Time Complexity: O(log n)

 Space Complexity: O(1) (iterative) / O(log n) (recursive).

Future Minds

You might also like