Unit-1 (Er.
Sukhwinder Kaur)
Difference between algorithm and flowchart
What is an Algorithm?
Algorithm refers to a set of rules/instructions that step-by-step define how a work is to be executed in order
to get the expected results.
A flowchart is a graphical representation of an algorithm. Programmers often use it as a program-planning
tool to solve a problem. It makes use of symbols that are connected among them to indicate the flow of
information and processing.
S.
No Algorithm Flowchart
An algorithm is a step-by-step procedure A flowchart is a diagram created with different shapes
1. to solve a problem. to show the flow of data.
2. The algorithm is complex to understand. A flowchart is easy to understand.
3. In the algorithm, plain text is used. In the flowchart, symbols/shapes are used.
4. The algorithm is easy to debug. A flowchart is hard to debug.
5. The algorithm does not follow any rules. The flowchart follows rules to be constructed.
Flowchart and its symbols
What is Basic Analysis of an Algorithm?
When we analyze an algorithm, we try to understand how good or efficient it is.
It is also consider as types of complexity.
1. How much time will it take? → Time Complexity
2. How much memory will it need? → Space Complexity
1. Time Complexity
It tells us how fast an algorithm runs.
We don’t measure in seconds, but in number of steps it takes.
Example: If an algorithm checks every item in a list of size n, we say Time Complexity = O(n).
2. Space Complexity
It tells us how much memory the algorithm needs to run.
Includes memory used for:
Variables
Input/output
Temporary storage
Types of Analysis
Type of Case Meaning Example
Searching first
Best Case Minimum time taken (ideal situation)
element in a list
Searching last element
Worst Case Maximum time taken (slowest)
in a list
Average Case Time taken on average Random position in list
Example:
Problem: Search a number in a list of 5 items
List: [4, 7, 2, 8, 6]
Best Case: Number is at 1st position → 1 step
Worst Case: Number is at 5th position → 5 steps
Average Case: Usually 3 steps
So Time Complexity = O(n), where n is the number of elements.
Summary:
Concept Meaning
Time Complexity Steps needed (Speed)
Space Complexity Memory needed
Best/Worst/Average Different situations for running time
What is Big-O Notation (O)
We use Big-O notation to express time and space complexity.
Big-O Notation Meaning Example
O(1) Constant time Accessing a specific element
O(log n) Logarithmic time Binary Search
O(n) Linear time Looping through array
O(n²) Quadratic time Nested loops
Comparison Table
Big-O Name Growth Rate Example
O(1) Constant time Very Fast Accessing array element
O(log n) Logarithmic time Fast Binary search
O(n) Linear time Moderate Simple loop
O(n²) Quadratic time Slow Nested loops
Steps to Find Big-O
Step 1: Identify input size (n)
Example: Array has n elements.
Step 2: Count operations
Look at loops/recursion.
Example:
for (int i = 0; i < n; i++) {
cout << i;
}
runs n times
Step 3: Pick the biggest term
Example: 5n^2 + 3n + 10 → biggest term = n^2
Step 4: Write in Big-O
Answer: O(n^2)
Time–Space Tradeoff
It means:
More memory → faster program
Less memory → slower program
O(1) → Constant Time
Steps do not depend on input size.
int getFirstElement(int arr[], int n) {
return arr[0]; // Always 1 step
}
Example: Finding the first element in an array.
No matter if array has 10 or 1 million elements → only 1 step.
2. O(n) → Linear Time
Steps increase linearly with n.
for (int i = 0; i < n; i++) {
cout << arr[i];
}
Example: Printing all elements in an array.
If n = 10, 10 steps.
If n = 1000, 1000 steps.
4. O(n²) → Quadratic Time
Two nested loops.
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << i << "," << j;
}
}
Example: Checking every pair of students in a class.
If n = 10, → 100 checks.
If n = 100, → 10,000 checks.
What is an Array?
An array is a type of linear data structure that is defined as a collection of elements with same or different data
types. They exist in both single dimension and multiple dimensions. These data structures come into picture
when there is a necessity to store multiple elements of similar nature together at one place.
Element − Each item stored in an array is called an element.
Index − Each location of an element in an array has a numerical index, which is used to identify the
element.
Syntax:
data_type array_name[array_size]={elements separated by commas} or, data_type array_name[array_size];
INT arr[2]={32,34};
General Representation
If an array is written as:
A[0], A[1], A[2], ... , A[n-1]
A = name of the array
n = number of elements (size of array)
Indexing usually starts from 0 in most programming languages (C, C++, Java, Python).
Example:
A[5] = {10, 20, 30, 40, 50}
Here,
A[0] = 10
A[1] = 20
A[2] = 30
A[3] = 40
A[4] = 50
3. Memory Representation
Arrays are stored in continuous memory blocks.
If the base address (starting address) of the array is BA, and each element takes W bytes, then the address of
element A[i] is:
Address of A[i] = BA + (i × W)
Where:
BA = base address of array (address of first element)
i = index of element
W = size of one element (in bytes)
Example
Suppose an integer array starts at address 2000, and each integer takes 4 bytes.
Array: A[4] = {5, 10, 15, 20}
Address of A[0] = 2000
Address of A[1] = 2000 + (1×4) = 2004
Address of A[2] = 2000 + (2×4) = 2008
Address of A[3] = 2000 + (3×4) = 2012
4. Types of Arrays
1. One-dimensional Array (1D):
o Linear collection of elements.
o Example: int A[5] = {2, 4, 6, 8, 10}
2. Two-dimensional Array (2D):
o Like a matrix (rows and columns).
o Example:
o int B[2][3] = { {1,2,3}, {4,5,6} }
This represents:
123
456
3. Multidimensional Arrays (3D, 4D...):
o Extension of 2D arrays.
o Example: 3D array is like a cube.
What is Recursion?
Recursion is a process in which a function calls itself directly or indirectly to solve a problem.
👉 Instead of repeating the same code again and again, the function keeps calling itself with a smaller version
of the problem until it reaches a base condition (a stopping point).
🔹 Structure of a Recursive Function
A recursive function has two parts:
1. Base Case (Stopping Condition):
This tells the function when to stop. Without this, recursion will go on forever.
2. Recursive Case:
This is the part where the function calls itself with a smaller or simpler input.
Let’s print numbers 1 to 4 using recursion and also go step by step
#include <iostream>
#include<conio.h>
void printNumbers(int n) {
if (n == 1) // base case (stopping condition)
return;
printNumbers(n - 1); // recursive call with smaller value
cout << n << " "; // print after recursive call
int main() {
printNumbers(4);
return 0;
Output:
1234
Difference between static memory allocation and dynamic memory allocation
1. Static Memory Allocation
Memory is decided before the program starts running (at compile time).
Size is fixed → once declared, it cannot change.
Stored in stack (or data segment).
Fast, but not flexible.
int arr[5]; // array of size 5 fixed at compile time
Here, memory for arr[5] is reserved permanently for 5 integers.
2. Dynamic Memory Allocation
Memory is decided while the program is running (at runtime).
Size is flexible → user/program can decide at runtime.
Stored in heap memory.
Slower, but very flexible.
int n;
cin >> n; // user gives size
int* arr = new int[n]; // create array of size n at runtime
If user enters n=8, memory for 8 integers will be created dynamically.
You can create arrays of any size depending on input.
Aspect Static Memory Allocation Dynamic Memory Allocation
Memory for variables is allocated before Memory for variables is allocated
Definition
execution (compile time). during execution (runtime).
Memory size is flexible and can be
Memory size is fixed once declared; cannot be
Flexibility allocated or reallocated as per
changed later.
requirement during execution.
Memory Area
Uses Stack or Data Segment of memory. Uses Heap memory.
Used
Faster because allocation happens at compile Slower because allocation takes place at
Speed
time. runtime and requires extra instructions.
May lead to wastage of memory if allocated
size is larger than required. Also may cause More efficient because you can allocate
Efficiency
overflow if required size is bigger than exact memory needed, reducing wastage.
allocated.
Done manually by programmer using
Implementation Done automatically by compiler. operators like new, delete (in C++), or
functions like malloc(), free() (in C).
More complex because programmer has
Very easy to implement (simply declare
Ease of Use to manage memory (allocation +
variables).
deallocation).