Introduction to Algorithms
Basic Concepts
What is a Program?
A program is a sequence of instructions executed by the computer.
What is an Instruction?
An instruction is one action the computer performs while running a program.
Examples of Instructions:
// Assignment
int x = 5;
x = x + 1;
// Comparison
if (x > 10)
// Output
cout << x;
Algorithms
What is an Algorithm?
An Algorithm is a sequence of well-defined instructions for solving a problem.
Why Study Algorithms?
- To know a standard set of important algorithms from different areas of computing.
- To be able to design new algorithms and analyze their efficiency.
Time Complexity Analysis
What is Time Complexity?
Time Complexity describes how many times program instructions are executed as the input size increases.
Important Clarification
- It is not the real time in seconds.
- It does not depend on computer speed.
- It depends on the number of executed instructions.
Why Do We Need Time Complexity?
- To compare different solutions.
- To know which program works better for large inputs.
- To avoid very slow programs.
Note: Time complexity depends on how many times instructions are executed.
Complexity Examples
1. Linear Time: O(n)
Problem: Find the sum of numbers from 1 to n.
int sum = 0;
for (int i = 1; i <= n; i++) {
sum = sum + i;
}Counting Instructions:
sum = 0→ executed 1 time- Loop runs → n times
sum = sum + i→ executed n times
The number of instructions increases linearly with n.
2. Constant Time: O(1)
Problem: Sum from 1 to n (Efficient Solution).
Instead of adding numbers one by one, we use a mathematical formula.
int sum = n * (n + 1) / 2;
Counting Instructions:
- Multiplication, Addition, Division, Assignment → Each 1 time
Total instructions = constant.
3. Quadratic Time: O(n²)
Problem: Nested Loops.
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << "Hello";
}
}Counting Instructions:
- Outer loop runs → n times
- Inner loop runs → n times for each iteration of outer loop
- Total inner body executions → n × n = n²