[Mastering Data Structures and Algorithms] Key Concepts and Complexity Analysis

Udemy

• Online course lectures up to the 45th

1. Data Structure

• Each data structure contains information about the data values, relationships between the data and functions that can be applied to the data

• staying inside the main memory during the execution

2. Database

• Collection of structure data used for storing, retrieving, adding, modifying, and deleting information

• Stored on a HDD (Hard Disk Drive Storage), and the data is typically arranged in tables

• RDBMS, Relational Database Management Systems are the most commonly used software to manage databases

3. Data Warehouse

• A large collection of data that is currently inactive.

• Collects data from various sources within an organization and uses that data to provide bussiness insights through analysis

• Typically, It preserve data over a long period of time, useful for historial analysis

4. Big data

• Large amounts of data accumulating daily on the internet

Physical VS Logical Data Structure

1. Physical Data Structure

• Manage how the data will be stored in the memory of a comptuer.

• Directly deals with the memory storage operations

• Array / Linked List

2. Logical Data Structure

• high-level, abstract data sturcture that help to organize and manipulate the data in a more efficient

• Not deal with the memory organization, But focus on the logical view or task

• Stack / Queue / Trees / Graph / Hash Table

3. ADT (Abstract Data Type)

• Encapsulate the data and operations it can be performed on the data.

• It does not reveal the internal working of the data structure, hence the term abstract

Why?

• It allows us to focus on what the data structure does

• It makes it easier to manage complex systems by separating the interface (what the system does) from the implementation (how the system does it).

• Example code

    class Stack:
        def __init__(self):
            self.stack = []
  
        # Operation: push
        def push(self, item):
            self.stack.append(item)
  
        # Operation: pop
        def pop(self):
            if len(self.stack) < 1:
                return None
            return self.stack.pop()
  
        # Operation: peek (view the top item)
        def peek(self): 
            if not self.stack:
                return None
            return self.stack[-1]
  
        # Operation: is_empty (check if the stack is empty)
        def is_empty(self):
            return not bool(self.stack)
  
        # Operation: size (get the size of the stack)
        def size(self):
            return len(self.stack)
  

• Data : self.stack and Operations : push, pop, peek, is_empty, size

Time & Space Complexity

1. Code

void swap(x,y)
{
	int temp;

	temp = x; // -> 1 (assignment)
	x = y;    // -> 1 (assignment)
	y = temp; // -> 1 (assignment)
}

Calculate the time complexity:

• f(n) = 3n^0 = O(n^0) = O(1)

int sum(int A[], int n)
{
	int s,i; 
	s = 0;              // -> 1 (assignment)

	for (i=0; i<n; i++) // -> n+1
	{
		s = s+A[i];     // -> n
	}
	return s;           // -> 1 (assignment)
}

Calculate the time complexity:

• f(n) = 2n + 3 = O(n)

1. Explanation

In this for loop

for (i=0; i<n; i++)

• i = 0

  It is assignment. 1

• i<n

  condition, So It is n but, we have to add +1 for the condtiion fail So, It is n+1

• i++

  It is n

• We can ignore all others (1 and n), so for loop takes n+1

2. Explanation

void Add(int n)
{
	int i,j;

	for (i=0;i<n;i++) 					 //-> n+1
	{
		for (j=0;j<n;j++) 				 //-> n*(n+1)
		{
			c[i][j] = A[i][j] + B[i][j]; //-> n*n
		}
	}
}

Calculate the time complexity:

• f(n) = 2n^2 + 2n + 1 = O(n^2)

3. Explanation

• n+1

  outer for loop (same principle above the only one for loop fucntion)

• n*(n+1)

  Outer loop iterates n times * Also, inner loop condition iterates n+1

• n*n

  Executed for each iteration of both outer and inner n*n