Semester 3 - Data Structure & Algorithm

Types of Notations for Time Complexity

• These notations illustrate how an algorithm’s time requirement grows with input size.
• They offer a relative measure of efficiency, not exact timings.

“N”-no. of steps, “n”-input size, From bottom, O(1)-constant, logarithmic-O(log n), square root-O(sqrt n) Linear-O(n), Log linear-O(n log n), Quadratic-O(n²), Exponential-O(2ⁿ), Worse-O(n!)

Big O Notation (O)

• Represents the worst-case scenario for an algorithm.
• Describes the upper limit of time taken.
• Example: O(n) means time increases linearly with input size.

Big Omega Notation (Ω)

• Represents the best-case scenario for an algorithm.
• Describes the lower limit of time taken.
• Example: Ω(n²) means time is at least proportional to the square of input size.

Big Theta Notation (Θ)

• Represents both best-case and worst-case scenarios.
• Defines the exact asymptotic behavior.
• Example: Θ(n log n) means time grows with n log n of input size.

Little o Notation (o)

• Gives an upper limit that is not tight.
• Function grows slower than this limit.
• Example: o(n) means function grows slower than linear time.

Little Omega Notation (ω)

• Gives a lower limit that is not tight.
• Function grows faster than this limit.
• Example: ω(1) means function grows faster than constant time.

Linear Data Structures

• Linear data structures store data in a sequential manner, and operations traverse linearly over elements.

Arrays

• Collection of elements of the same type.
• Elements stored in contiguous memory locations.
• Supports random access using indices.
• Insertion and deletion operations are time-consuming.
• Memory allocated at compile time (static memory allocation).
• Size must be specified at declaration.

int[] arr = new int[5]; // Declare an array
arr[0] = 1; // Access array elements
arr[1] = 2;

Linked Lists

• Linear data structure with each element as a separate object.
• Each element (node) contains data and a reference to the next node.
• Last node references null, entry point is the head of the list.
• Operations include insertion, deletion, display, search, and update.

import java.util.LinkedList;

LinkedList<String> linkedList = new LinkedList<>(); // Declare a linked list
linkedList.add("Element1"); // Add elements
linkedList.add("Element2");

Three types of lists

Singly-linked list

• All elements except the last have a reference to the next element in the list.

Singly linked list

Circular list

• This type is similar to the single-chained one, but the last element has a reference to the first.

Circular linked list

Double-linked list

• The elements in the list have both a reference to the previous and the following element.

Doubly linked list

Stacks

• LIFO (Last In First Out) or FILO (First In Last Out) structure.
• Operations include push, pop, and peek or top.
• Insertion and removal occur at one end, the top.
• Can be implemented using arrays or linked lists.
• Used in applications like reversing a word, parsing, and expression conversion.

import java.util.Stack;

Stack<Integer> stack = new Stack<>(); // Declare a stack
stack.push(10); // Push elements onto the stack
stack.push(20);
int topElement = stack.peek(); // Peek the top element

Basic operations of a stack

Queues

• FIFO (First In First Out) data structure.
• Operations include enqueue (add), dequeue (remove), front/head (at dequeue side), and rear/tail (at enqueue side).
• Insertion and removal follow the first in, first out principle.
• Can be implemented using an array, stack, or linked list.
• Used when managing a group of objects where the first one in is also the first one out.

import java.util.Queue;
import java.util.LinkedList;

Queue<Integer> queue = new LinkedList<>(); // Declare a queue
queue.add(10); // Enqueue elements
queue.add(20);
int frontElement = queue.peek(); // Peek the front element

Queue vs Stack

Infix, Prefix and Postfix expressions

In-fix: The operator is in between the two operands that it is working on. Example: A + B

Pre-fix (or Polish Notation): The operator is prefixed to operands, i.e., the operator is placed before the operands. For example, +AB

Post-fix (or Reverse Polish Notation: The operator is postfixed to the operands i.e., the operator is placed after the operands. For example, AB+

Equation (Infix)	Prefix Notation	Postfix Notation	Solution
(2 + 3) * 4	* + 2 3 4	2 3 + 4 *	20
4 * (5 + 6)	* 4 + 5 6	4 5 6 + *	44
(7 - 2) / (3 + 2)	/ - 7 2 + 3 2	7 2 - 3 2 + /	1
8 / (2 * (3 - 1))	/ 8 * 2 - 3 1	8 2 3 1 - * /	2
(9 + 4) * (6 - 2)	* + 9 4 - 6 2	9 4 + 6 2 - *	52

Infix to Postfix string

Infix Equation: ((A-(B+C))*D)^(E/F)

1. Read the equation from left to right.
2. Output operands (like A, B, C) immediately.
3. If the incoming symbol is ‘(‘, push it onto the stack.
4. If it’s an operator (+, -, *, /, ^), pop operators from the stack to the output until you find an operator with less priority or a ‘(‘ on the stack. Then push the incoming operator.
5. If the incoming symbol is ‘)’, pop operators from the stack to the output until you find ‘(‘. Pop and discard ‘(‘ from the stack.
6. If the incoming symbol is end of the equation, pop all remaining operators from the stack to the output.
7. Repeat steps 2-6 until the equation is read completely.
8. Now, the output is your postfix equation.

This results in the postfix string A B C + - D * E F / ^.

Symbol	Postfix String	Stack
(		(
(		((
A	A	((
-	A	((-
(	A	((-(
B	A B	((-(
+	A B	((-(+
C	A B C	((-(+
)	A B C +	((-
*	A B C +	((*
D	A B C + D	((*
)	A B C + D *	(
^	A B C + D *	(^
(	A B C + D *	(^ (
E	A B C + D * E	(^ (
/	A B C + D * E	(^ (/
F	A B C + D * E F	(^ (/
)	A B C + D * E F/	(^
(End)	A B C + D * E F/^

Evaluating Postfix

Visual example

Steps to evaluate a postfix expression

1. Start reading the postfix expression from left to right.
2. If the symbol is an operand (i.e., a number or variable), push it onto the stack.
3. If the symbol is an operator (i.e., +, -, *, /, ^), then:
   • Pop two operands from the stack. The first popped operand is the second operand of the operator, and the second popped operand is the first operand.
   • Perform the operation (e.g., addition, subtraction, etc.) on the two operands.
   • Push the result back onto the stack.
4. Repeat steps 2-3 until the postfix expression is read completely.
5. At the end of the evaluation, the stack will contain only one item — the final result. So, pop and return it.