‫جامعة السرايا الحمراء‬

Saraya Hamra University

Computer Algorithms & Data

Structures (CSE232)
Topic#1
Algorithm Analysis
Instructor: Asma Elassar
Fall 2025
 Introduction ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• What is Computer algorithm?

• It is ‘’a set of steps to accomplish or complete a task that is described
precisely enough that a computer can run it’’.
• An algorithm is a step-by-step set of instructions for solving a problem or
accomplishing a task.
• What is a program?
• It is an algorithm that has been encoded into some programming language
• What is a data structure?
• It is a systematic way of organizing and accessing data

2
 Characteristics of good algorithm
‫جامعة السرايا الحمراء‬
Saraya Hamra University

• Well-Defined Steps: Each instruction must be clear, precise, and

unambiguous. It cannot be open to interpretation.
• Inputs: It has zero or more clearly defined inputs.
• Outputs: It produces one or more clearly defined outputs (the
solution to the problem).
• Finiteness: It must terminate after a finite number of steps. It cannot
run forever.
• Effectiveness: Each step must be simple and feasible to perform,
ideally with a pencil and paper. It must be "doable."
• Deterministic: For the same given input, the algorithm will always
produce the same output.
3
 Key Concepts in Computer Science ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• In computer science, algorithms are the foundation of all programs.

• Algorithm vs. Program: An algorithm is the abstract idea or the
blueprint. A program is the concrete implementation of that
algorithm written in a specific programming language (like Python,
Java, or C++).
• Flowcharts & Pseudocode: Before writing code, programmers often
design algorithms using flowcharts (visual diagrams)
or pseudocode (a simplified, human-readable version of code). This
helps in planning the logic.

4
 A Simple Programming Example:
Finding the Largest Number ‫جامعة السرايا الحمراء‬
Here is a simple algorithm to find the largest number in a list. Saraya Hamra University

• Problem: Find the largest number in a list.

• Input: A list of numbers (e.g., [8, 3, 12, 5, 9]).
• Output: The largest number (e.g., 12).

Algorithm in Pseudocode:

• Assume the first number in the list is the largest. Call it max.
• Look at the next number in the list.
• If that number is greater than max, then set max to be that number.
• Repeat steps 2 and 3 for all remaining numbers in the list.
• After checking all numbers, the value stored in max is the largest number. Output max.

5
 A Simple Programming Example:
Finding the Largest Number ‫جامعة السرايا الحمراء‬
Here is a simple algorithm to find the largest number in a list. Saraya Hamra University

• Problem: Find the largest number in a list.

• Input: A list of numbers (e.g., [8, 3, 12, 5, 9]).
• Output: The largest number (e.g., 12).

Algorithm in Pseudocode:

• Assume the first number in the list is the largest. Call it max.
• Look at the next number in the list.
• If that number is greater than max, then set max to be that number.
• Repeat steps 2 and 3 for all remaining numbers in the list.
• After checking all numbers, the value stored in max is the largest number. Output max.

6
A Simple Programming Example:
Finding the Largest Number ‫جامعة السرايا الحمراء‬
Saraya Hamra University

7
 Why Algorithms Are So Important?
‫جامعة السرايا الحمراء‬
Saraya Hamra University

•Efficiency: A good algorithm solves a problem quickly and with

minimal resources (like memory). For example, Google's search
algorithm can sift through billions of webpages in milliseconds.
•Scalability: Efficient algorithms allow systems to handle larger
amounts of data without a significant drop in performance.
•Automation: They are the core of automation, enabling computers
to perform complex tasks without human intervention.
•Foundation of Computing: Everything a computer does, from sorting
your contacts to rendering a complex video game, is driven by
algorithms.

8
 Algorithm Analysis ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• Algorithm analysis is concerned with comparing algorithms based on

computing resources that each algorithm uses.

• Computing resources:
1. The amount of space required by data structures (space complexity)
2. Amount of time they require to execute the algorithm (time
complexity)

9
 Algorithm Analysis ‫جامعة السرايا الحمراء‬

• Example: compute the sum of n integers

Saraya Hamra University

10
 Algorithm Analysis ‫جامعة السرايا الحمراء‬

• Example:
Saraya Hamra University

11
 Algorithm Analysis ‫جامعة السرايا الحمراء‬
• Example II: Saraya Hamra University

compute the sum of n integers, when n=10,000 , 100,000 , 1,000,000,

10,000,000
import time
def sum_n3(n):
sum=0
start=[Link]()
for i in range(n+1):
sum+=i
end=[Link]()
return sum,end-start

print('Sum is ',sum_n3(10000))
print('Sum is ',sum_n3(100000))
print('Sum is ',sum_n3(1000000))
print('Sum is ',sum_n3(10000000))
print('Sum is ',sum_n3(100000000)) 12
 Algorithm Analysis ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• using five different values for n (10,000, 100,000, 1, 000,000, 10,000,000,

and 100,000,000), we get the following results:

• From the previous examples, we can see that running time of algorithm
depends on the size of the input n
• As n gets bigger as running time gets longer.
13
Algorithm Analysis
‫جامعة السرايا الحمراء‬
Saraya Hamra University

14
 Key Concepts in Algorithm Analysis
1. Computational Resources
‫جامعة السرايا الحمراء‬
The two main resources we analyze are: Saraya Hamra University

Time Complexity: How long does the algorithm take to run? (Number of operations)
Space Complexity: How much memory does the algorithm use?

Time complexity is usually the primary focus.

2. Input Size (n)

We describe the efficiency of an algorithm as a function of the size of its input, denoted by n.

For sorting, n is the number of items to sort.

For searching a graph, n might be the number of nodes or edges.

The central question is: "As n grows, how do the time/space requirements grow?"

3. Rate of Growth (Orders of Growth)

We care most about how the resource requirements grow as n becomes very large. This is called asymptotic
analysis. Constants and lower-order terms become insignificant for large n, so we ignore them.
15
 Time Complexity (example) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

Algorithm to find prime numbers Example: Check if 5 is prime

2,3,5,7,11….etc 5/2=2.5
5/3=1.66
5/4=1.25

12345 Example: check if 9 is prime

9/2=4.5
9/3=3 (Stop it’s not prime number)

16
 Time Complexity
Comparing two algorithms ‫جامعة السرايا الحمراء‬
Saraya Hamra University
[Assume 1ms for division]
Algorithm (1) Algorithm (2)
For i=2 to N-1 For i=2 to √N
if N divisible by i VS if N divisible by i
N is not prime N is not prime

End End
Iterations : N-2 Iterations : √N -1
N=11 Takes (11-2)=9ms N=11 Takes (3-1)=2ms
N=101 Takes 99ms N=101 Takes 9ms
N=10^6+3 Takes 10^6ms->16.6 min N=10^6+3 Takes 10^3ms->1sec
N=10^10 + 19 Takes 10^10ms->115 day N=10^10 + 9 Takes 1.6 min 17
 Time Complexity Analysis ‫جامعة السرايا الحمراء‬
Saraya Hamra University

Computer A Computer B

5 sec 10 sec
Factors:
1. Single processor/multi-processor
2. Core speed
3. Read/write RAM
Algorithm 4. Programming Language
5. Compiler
6. Input

18
 Time Complexity
Frequency Count Method ‫جامعة السرايا الحمراء‬
Saraya Hamra University

Function sum(a,b)
Result = a+b --------- (1) • Arithmetic operations – 1 unit of time
return result --------(1) • Assignment operator – 1 unit of time
End Function
• Comparison – 1 unit of time
Function ArraySum(arr,n)
• return statement – 1 unit of time
Sum=0 -------------------- 1
for i in range(0,n,1): -----2n+2
sum+=sum+arr[i] -----2n
return sum ----------------------1 ‫تعد هذه الطريقة عدد األسطر في الخوارزمية و تحسب قيمة‬
‫الدالة‬
End Function f(n)

19
 Time Complexity
Frequency Count Method (Exercise) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

Example
Calculate the time function of the following sub-program (cost)
Printing elements of 2-d array
Function print2DArray(arr,n)
for (i=0;i<n;i++) ---------------->1+(n+1) +n=2n+2------>n
for(j=0;j<n;j++) ------------> n(‫ )عدد تكرار الحلقة األولى‬x n(‫=)عدد تكرار الحلقة الحالية‬n**2
print(arr[i,j])------------> n x n=n**2
End Function

f(n)=2n**2+n

20
 Time Complexity
Frequency Count Method (Exercise) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

Calculate the time function of the following sub-program (cost)

i=1
i
n=10 -----------------
While(i<n) 1x2=21
{ 2x2=22 = 4
22 x2=23 = 8
i*=2 23 x2=24 = 16
}
𝑖 = 2𝑘 = 𝑛
𝑘 = log 2(𝑛)
log 2 16 = 4
𝑓(𝑛) = 2 log 2 𝑛 + 2

21
22
 Comparing Growth Rate ‫جامعة السرايا الحمراء‬
Saraya Hamra University

Order of functions used in algorithm analysis

• we would like our algorithms to run in linear or n-log-n time.

• Algorithms with quadratic or cubic running times are less practical
• exponential running times are infeasible for all but the smallest sized
inputs

23
Comparing Growth Rate ‫جامعة السرايا الحمراء‬
Saraya Hamra University

24
 Asymptotic Notations
Big-O Notation ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• Big-O Notation is the most widely used method which describes algorithm
complexity:
• the execution time required or
• the space used in memory or in disk by an algorithm

• Big-O notation is used describe the rough estimate of the number of

“steps” to complete the algorithm
• It is the mathematical language we use to describe an algorithm's upper
bound performance—its worst-case scenario. It formalizes the concept of
the "rate of growth."

25
Big-O for time complexity ‫جامعة السرايا الحمراء‬
Saraya Hamra University

26
 Rules summary for big-O ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• O(1) * O(n) = O(n)

• O(n) * O(n) = O(n2)
• O(1) + O(n) = O(n)
• O(n) + O(n2) = O(n2)
• O(1) + O(n) + O(n2) = O(n2)
• Comparison of increase speed:
• O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n2)

27
 ‫جامعة السرايا الحمراء‬
Saraya Hamra University

28
Asymptotic Analysis ‫جامعة السرايا الحمراء‬
Saraya Hamra University

29
 Comparison of Algorithms ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• Often algorithm with smaller big-O notation is more efficient

• But it may not be correct for small scale of data
• But this rule will be efficient for very large number of data
• Because computer science is always dealing with large scale of data
this rule is applicable

30
 Time functions to measure ‫جامعة السرايا الحمراء‬
Saraya Hamra University

Time complexity
1. The constant function
2. The Logarithm function
3. The Linear function
4. The N-log-N function
5. The quadratic function
6. The Cubic function and other polynomials
7. The Exponential function

31
 The constant function ‫جامعة السرايا الحمراء‬
Saraya Hamra University

If the complexity function f is constant, i.e. f(n) = c

for some fixed value c, t
Hence, we say f = O(1).
Such as: c-5, c=27, or c=210

32
 The Logarithm Function ‫جامعة السرايا الحمراء‬
Saraya Hamra University

This function is defined as follows:

𝑥 = log 𝑏 𝑛 𝑖𝑓 𝑎𝑛𝑑 𝑜𝑛𝑙𝑦 𝑖𝑓 𝑏 𝑥 = 𝑛

log 𝑏 1 = 0 𝑤ℎ𝑒𝑟𝑒 𝑏 𝑖𝑠 𝑡ℎ𝑒 𝑏𝑎𝑠𝑒 𝑜𝑓 𝑙𝑜𝑔𝑎𝑟𝑖𝑡ℎ𝑚

Note that, the base for computer science is 2
Thus, for us, log 𝑛 = log 2 𝑛
Proposition 1: Given real numbers a>0, b>1, c>0, and d>1, we have:

33
 The Logarithm Function ‫جامعة السرايا الحمراء‬
Saraya Hamra University

Examples:

34
 The Linear Function ‫جامعة السرايا الحمراء‬
Saraya Hamra University

Simple but important function

𝑓 𝑛 =𝑛
This function arises to do a single basic operation for each of n
elements.
For example:
Comparing a number x to each element of a sequence of size n, will
require n comparisons.

35
 The N-Log-N Function ‫جامعة السرايا الحمراء‬
Saraya Hamra University

The n-log-n function:

𝑓 𝑛 = 𝑛𝑙𝑜𝑔𝑛

This function grows a little more rapidly than the linear function and a
lot less rapidly than the quadratic function
For example, that fastest possible algorithms for sorting n arbitrary
values

36
 The Quadratic Function ‫جامعة السرايا الحمراء‬
Saraya Hamra University

The quadratic function:

𝑓 𝑛 = 𝑛2
Example:
Using nested loops, where the inner loop performs a linear number of
operations
The outer loop is performed linear number of times.

Thus, the algorithm performs: 𝑛. 𝑛 = 𝑛2 operations.

37
The Cubic Function and other Polynomials ‫جامعة السرايا الحمراء‬
Saraya Hamra University

The cubic function:

𝑓 𝑛 = 𝑛3
Polynomial function has the form,
𝑓 𝑛 = 𝑎0 + 𝑎1 𝑛 + 𝑎2 𝑛2 + ⋯ + 𝑎𝑑 𝑛𝑑

Where 𝑎0 , 𝑎1 , … , 𝑎𝑑 are constants, called the coefficients of the

polynomial, and 𝑎𝑑 ≠ 0
Integer d is the degree of the polynomial

38
The Cubic Function and other Polynomials ‫جامعة السرايا الحمراء‬
Saraya Hamra University

For example, the following functions are polynomials:

𝑓 𝑛 = 2 + 5𝑛 + 𝑛2
𝑓 𝑛 = 1 + 𝑛3
𝑓 𝑛 =1
𝑓 𝑛 =𝑛
𝑓 𝑛 = 𝑛2

39
 The Exponential Function ‫جامعة السرايا الحمراء‬
Saraya Hamra University

The exponential function has the form,

𝑓 𝑛 = 𝑏𝑛
Where b is the base and is the exponent
Important exponent rules:

For Example, we have the following:

40
 ‫جامعة السرايا الحمراء‬
Saraya Hamra University

41
 Other Asymptotic Notations
Big-Omega (Ω) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

➢ Big-Omega notation specifically describes best case

scenario
➢ It represents the lower bound running time complexity
of an algorithm
➢ Basically it tells you what is the fastest time/behavior in
which algorithm can run.
Mathematically:
Let f and g be functions of n where n is denoting the
number of steps of algorithm, then:
f(n)= Ω(g(n)) iff:
f(n)>=c.g(n) where n>=n0, c>0, n0>1

42
 Other Asymptotic Notations
Big-Theta (Θ) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

➢ Big-Theta notation specifically describes average case scenario

➢ It represents the most realistic time complexity of an algorithm
Mathematically
Let f and g be functions of n, where:
n is denoting size of steps of the algorithm, then:
f(n)= Θ(g(n)) iff:
c1.g(n) <=f(n)<=c2.g(n), where:
n>n0, c1 and c2>0, n>n0, n0>=1

43
 ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• It is also important to note that if 𝑓(𝑛) = 𝑂(𝑔(𝑛)) and = h(𝑛) = 𝑂(𝑔(𝑛)),

then it does not follow that 𝑓 (𝑛) = h(𝑛).
• For example,

• but

44
 ‫جامعة السرايا الحمراء‬
Saraya Hamra University

45
 Exercise (1) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• Prove that 2𝑛2 = 𝑂 𝑛3

Answer:

𝑓 𝑛 ≤ 𝑐. 𝑔 𝑛
2𝑛2 ≤ 𝑐. 𝑛3 𝑑𝑖𝑣𝑖𝑑𝑒 𝑛2 𝑜𝑛 𝑏𝑜𝑡ℎ 𝑠𝑖𝑑𝑒𝑠
2 ≤ 𝑐. 𝑛
We have to find the value of c and 𝑛0
𝑛0 = 1
Then c value equals to 2
2 ≤ 𝑐 ⇒ 𝑐 = 2, 𝑛0 = 1
Then this is proved
46
 Exercise (2) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• Prove that 𝑛2 = 𝑂 𝑛2
Answer:

𝑓 𝑛 ≤ 𝑐. 𝑔 𝑛
𝑛2 ≤ 𝑐. 𝑛2
We have to find the value of c and 𝑛0
n0 = 1 and c=1
1≤1
Then this is proved

47
 Exercise (3) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• Prove or disprove that 𝑛3 = 𝑂 𝑛2

Answer:

𝑓 𝑛 ≤ 𝑐. 𝑔 𝑛
𝑛3 ≤ 𝑐. 𝑛2 This inequality is not true
for n ≥ n0 is not true
𝑓𝑜𝑟 𝑎𝑛𝑦 𝑐𝑜𝑚𝑏𝑖𝑛𝑎𝑡𝑖𝑜𝑛 𝑜𝑓 𝑐 𝑎𝑛𝑑 𝑛0
Hence so, 𝑛3 ≠ 𝑐. 𝑛2 ⇒ 𝑛3 ≠ 𝑂(𝑛2 )

48
 Exercise (4) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• Prove that 2𝑛 + 10 = 𝑂 𝑛
Answer:

𝑓 𝑛 ≤ 𝑐. 𝑔 𝑛
2𝑛 + 10 ≤ 𝑐. 𝑛
10 ≤ 𝑐. 𝑛 − 2𝑛
10 ≤ 𝑐 − 2 𝑛
10
≤𝑛
(𝑐 − 2)
10
𝑐 ≠ 2 𝑏𝑒𝑐𝑎𝑢𝑠𝑒 ≤ 𝑛 Which means 𝑛 → ∞
2
𝑐 > 2 ⇒ 𝑐 = 3, 𝑛0 = 10
Then this has been proven 49
 Exercise (5) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• Prove that 3𝑛 + 2 = Ω(𝑛)?

Answer:

𝑐. 𝑔 𝑛 ≤ 𝑓 𝑛
𝑐. 𝑛 ≤ 3𝑛 + 2
𝑐. 𝑛 − 3𝑛 ≤2
n 𝑐−3 ≤2
2
𝑛≤ ⇒ 𝑐 = 4, 𝑛0 = 2
𝑐−3
Then this has been proven

50
 Exercise (6) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• Prove that 5. 𝑛2 = Ω(𝑛)?

Answer:

𝑐. 𝑔 𝑛 ≤ 𝑓 𝑛
𝑐. 𝑛 ≤ 5. 𝑛2
Divide both sides by n
𝑐 ≤ 5. 𝑛 ⇒ 𝑛0 =1 and c=5
Then this has been proven

51
 Exercise (7) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• Prove that 5. 𝑛2 + 2𝑛 − 3 = Ω(𝑛2 )?

Answer:

𝑐. 𝑔 𝑛 ≤ 𝑓 𝑛
𝑐. 𝑛2 ≤ 5. 𝑛2 +2n-3
We need to prove that (2n-3)>=0
3
2𝑛 ≥ 3 ⇒ 𝑛 ≥ ⇒ 𝑛 ≥ 2
2
𝑐 = 5, 𝑛0 =2
Then this has been proven
52
 Exercise (8) ‫جامعة السرايا الحمراء‬
Saraya Hamra University

• Prove that 100. 𝑛 + 5 = Ω(𝑛2 )?

Answer:

𝑐. 𝑔 𝑛 ≤ 𝑓 𝑛
𝑐. 𝑛2 ≤ 100. 𝑛 + 5
This cannot be proven because RHS is greater
𝑓𝑜𝑟 𝑛 ≥ 𝑛0
𝑐. 𝑛2 ≠ 100. 𝑛 + 5 ⇒ 100. 𝑛 + 5 ≠ Ω(𝑛2 )

53
 Exercise (9)
1 2 1
• Prove that .𝑛 − .𝑛 = 𝜃(𝑛2 )? ‫جامعة السرايا الحمراء‬
Saraya Hamra University
2 2
Answer:
𝑐1 . 𝑔 𝑛 ≤ 𝑓 𝑛 ≤ 𝑐2 . 𝑔(𝑛)
2 1 2 1
𝑐1 . 𝑛 ≤ .𝑛 − .𝑛 ≤ 𝑐2 . 𝑛2
2 2
1 2 1 1 2 1
𝑐1. 𝑛2 ≤ .𝑛 − .𝑛 .𝑛 − .𝑛 ≤ 𝑐2 . 𝑛2
2 2 2 2
1
1
Let’s assume 𝑐1 = Let’s assume 𝑐2 =
4 2
1 2 1 2 1 1 2 1 1 2
.𝑛 ≤ .𝑛 − .𝑛 .𝑛 − .𝑛 ≤ .𝑛
4 2 2 2 2 2
1 2 1 2 1 𝑛0 ≥ 1
0 ≤ .𝑛 − 𝑛 − .𝑛
2 4 2
1 2 1
.𝑛 − 𝑛
4 2
𝑛0 = 2 54