Chapter 1: Foundations and
Analysis of Algorithms 💻
1. Introduction to Algorithms
An algorithm is a precise,
unambiguous sequence of steps
or instructions designed to solve
a specific problem or perform a
computation. It is the core logic
behind any computer program.
1.1 Key Characteristics of a
Good Algorithm
* Input: Must accept zero or
more inputs (quantities that are
externally supplied).
* Output: Must produce at least
one output (a result).
* Definiteness: Each instruction
must be clear and unambiguous.
* Finiteness: Must terminate
after a finite number of steps for
all cases.
* Effectiveness: Every operation
must be basic enough that it can
be carried out, in principle, by a
person using only paper and
pencil.
1.2 Algorithm Representation
Algorithms are typically
represented using two primary
methods before implementation:
| Method | Description | Example
(Max of 3: A, B, C) |
|---|---|---|
| Pseudocode | An informal high-
level description of the operating
principle of a computer program
or algorithm. It uses structured
programming conventions (like
IF-THEN-ELSE, WHILE, FOR). |
IF A > B AND A > C THEN
RETURN A |
| Flowchart | A graphical
representation of the algorithm's
logic flow, using geometric
shapes to denote steps and
arrows to show the sequence. |
Diamond (Decision), Rectangle
(Process), Oval (Start/Stop) |
2. Algorithm Analysis: Complexity
Algorithm Analysis is the process
of determining the resources
(time and space) required by an
algorithm to execute. This allows
us to compare and select the
most efficient algorithm for a
given task.
2.1 Time Complexity
Time Complexity T(n) measures
the amount of time an algorithm
takes to run as a function of the
input size n. It is usually
calculated by counting the
number of elementary operations
performed (e.g., comparisons,
assignments, arithmetic
operations).
2.1.1 Notations for Execution
Time
To formalize the analysis of
execution time, we use
Asymptotic Notations (Big O, Big
Omega, and Big Theta), which
focus on the growth rate of the
algorithm's running time as the
input size n approaches infinity.
| Notation | Name | Definition |
Focus |
|---|---|---|---|
| Big O (O) | Worst-Case Time |
Upper Bound on the running
time. Guarantees that the
algorithm's time will not exceed
this limit. | Maximum time
required. |
| Big Omega (\Omega) | Best-
Case Time |
Lower Bound on the running
time. Guarantees the algorithm
will take at least this amount of
time. | Minimum time required. |
| Big Theta (\Theta) | Average-
Case Time | Tight Bound (both
upper and lower) on the running
time. Describes the exact
expected performance. | Typical
time required. |
Example of Time Complexity:
* Linear Search:
* Best Case (\Omega(1)): The
target element is found at the
first position.
* Worst Case (O(n)): The target
element is at the last position or
not in the array at all.
* Average Case (\Theta(n)):
The target is found somewhere
in the middle (requires n/2
comparisons).
2.2 Space Complexity
Space Complexity S(n) is a
measure of the amount of
memory (space) an algorithm
needs to run to completion,
expressed as a function of the
input size n.
Total space required is divided
into two parts:
* Fixed Part: Space for the code,
constants, simple variables.
Independent of n.
* Variable Part: Space required
by variables whose size depends
on n (e.g., array size, recursion
stack). Dependent on n.
In Big O notation, space
complexity usually refers to the
Variable Part as it dictates how
memory usage scales.
| Complexity Class | Growth Rate
| Example Algorithm |
|---|---|---|
| O(1) | Constant | Finding the
maximum of three numbers. |
| O(n) | Linear | Storing an array
of size n. |
| O(n^2) | Quadratic | Storing a
two-dimensional matrix of size n \
times n. |
3. Fundamental Algorithm
Examples
3.1 Finding the Maximum of
Three Numbers (A, B, C)
This is a O(1) (Constant Time)
algorithm because the number of
comparisons is fixed (a
maximum of two comparisons
are performed, regardless of the
input values).
Pseudocode (Sequential
Comparison):
ALGORITHM
FindMaximumOfThree
1. START
2. READ A, B, C
3. SET Max ← A //
Initialization: Max holds the
highest value found so far.
4. IF B > Max THEN
5. Max ← B //
Update Max if B is greater.
6. END IF
7. IF C > Max THEN
8. Max ← C //
Update Max if C is greater than
the current Max (A or B).
9. END IF
10. DISPLAY Max
11. STOP
Flowchart Logic: The algorithm
proceeds sequentially, using two
independent Decision symbols
(Diamonds) to check B and C
against the running Max variable.
3.2 Linear Search for the Largest
Subscript
The goal is to find the index
(subscript) of the last occurrence
of a target_value in an array of
size n.
Algorithm Rationale: We use a
simple Linear Search (checking
every element). By traversing the
array from the beginning to the
end, and updating the
largest_subscript every time the
target is found, the variable will
naturally hold the index of the
last match when the loop
terminates.
Time Complexity: \Theta(n)
* The algorithm must check
every element n times to ensure
it finds the largest subscript,
even if the target is found early.
Thus, the best, worst, and
average cases
are all linear.
C Function Implementation:
/**
* Finds the largest subscript
(index) of a target value in an
array.
* @param array The array to
search.
* @param size The number of
elements in the array.
* @param target_value The
value to find.
* @return The largest subscript,
or -1 if not found.
*/
int location_of_target(int array[],
int size, int target_value) {
// Initialized to -1 (Sentinel
value for 'not found')
int largest_subscript = -1;
// Loop through every element
from index 0 to size-1
for (int i = 0; i < size; i++) {
if (array[i] == target_value) {
// Update the
largest_subscript every time a
match is found.
// Since i is increasing,
the last value assigned to
// largest_subscript will be
the index of the last occurrence.
largest_subscript = i;
}
}
return largest_subscript;
}
4. Procedural Programming
Concepts
4.1 Weighted Average
Calculation
In educational and statistical
contexts, a weighted average is
calculated to give different
components (marks) a varying
degree of importance
(coefficient).
Formula:
\text{Weighted Average} = \frac{\
sum (\text{Mark}_i \times \
text{Coefficient}_i)}
{\sum \text{Coefficient}_i}
Where:
* \sum (\text{Mark}_i \times \
text{Coefficient}_i) is the Total
Weighted Marks.
* \sum \text{Coefficient}_i is the
Total Coefficient.
C Programming Logic:
* Initialization: Set
total_weighted_marks = 0 and
total_coefficient = 0.
* Iteration (Loop): Use a for loop
to process each subject.
* Accumulation: Inside the loop,
for each subject, calculate the
weighted mark and add it to
total_weighted_marks. Also, add
the subject's coefficient to
total_coefficient.
* Final Calculation: After the
loop, divide
total_weighted_marks by
total_coefficient to get the final
average.
4.2 Conditional Logic for Grading
(Remark)
Grading and remarks rely heavily
on
conditional statements (if, else if,
else) to map a numerical score to
a categorical outcome.
Example Logic (Sequential
Execution):
The conditions must be ordered
carefully to ensure correctness
(e.g., checking the lowest range
first or using boundary checks).
// Remark Logic:
if (average <= 6) {
// This executes if average is
between 0 and 6
printf("very poor");
} else if (average <= 9) {
// This executes ONLY IF
average is > 6 AND <= 9
printf("poor");
} else if (average < 10) {
// This executes ONLY IF
average is > 9 AND < 10
printf("below average");
} else if (average == 10) {
printf("average");
} else {
// This executes if all above
are false (i.e., average > 10)
printf("good");
}