ARBA MINCH INSTITUTE OF TECHNOLOGY

FACULTY OF ELECTRICAL AND COMPUTER ENGINEERING

(Stream Computer Engineering)

Course: Algorithm and Analysis Design

Chapter-one:Algorithm Analysis Basics
Name of members ID

1. Dawit Sheleme……………………………………………NSR/722/14
2. Iyob Zarihun...…………………………………………….NSR/1701/14
3. Rohobot Kolaso...…………………………………………NSR/1911/14
4. Yonas Gezahegn.………………………………………… NSR/2984/14
5. Lukas Mengistu……………………………………………NSR/1741/14
6. Gediyon Shewa……………………………………………NSR/2345/14
7. Bereket Asmare……………………………………………NSR/604/14

Submitted to: instructor: Fasika.T

Date of submission: 10-12-2025

Overview

Understanding how algorithms perform is a fundamental part of computer engineering, and

this involves studying time complexity, time–space trade-offs, worst-case and average-case
analysis, and mathematical notations such as Big-O, Big-Theta, and Big-Omega. Time
complexity helps us measure how the running time of an algorithm grows with the input size,
often demonstrated with simple examples like a Java loop that runs n times. At the same time,
algorithm design requires balancing speed and memory, which is explained through the time–
space trade-off. To evaluate performance more accurately, we compare how an algorithm
behaves in different situations using worst-case and average-case analysis. Finally, formal
notations like Big-O, Big-Theta, and Big-Omega provide a unified way to describe the upper
bound, exact bound, and lower bound of an algorithm's growth. Together, these concepts form
the basis for analyzing and selecting efficient algorithms.

I
 Figures

Figure 1 Graphic example of Theta…………………………………………………………11

Figure 2 Graphic example of Big O………………………………………..………………13

Figures 3 Graphic example of Ω………………………………………………………..…..15

Image

Image 1 :Software Development Life Cycle…………………………………………………5

II
Table contents

Overview…………………………………………………………………………………………….……..I

Figures and Image……………………………………………….………………………………….…II

Chapter 1 Algorithm Analysis Basics

1.1 Introduction to Algorithm……………………………………………………………………………….……….1

1.2 Algorithm vs Program………………………………………………………………………..….……….……….2

1.3 Properties of an algorithm……………………………………………………………….…………….……….5

1.4 Problems Solved by Algorithms…………………….………………………………………………….……..6

1.5 why Analyzing Algorithms?………………………………………………………………………………..……6

1.6 Order of Growth…………………………………………………………………………….……………………….8

1.7 Asymptotic Notations……………………………………………………………………….……………..……..8

1.7.1 Θ-Notation (Theta Notation)………………………………………………………………..……….10

1.7.2 Big-O Notation (O-notation)…………………………………………………………………..……….12

1.7.3 Big-Omega (Ω) Notation…………………………………………………………………………….……14

1.8 Comparing Worst-Case and Average-Case Analysis…………………………………………..…….15

1.8.1Worst-case Analysis…………………………………………………………………………………………15

1.8.2 Average-case Analysis……………………………………………………………………………….…...16

1.8.3 Best-case Analysis……………………………………………………………………………………….…16

1.9 Time vs. Space Trade-Offs…………………………………………………………………………………….…17

[Link] Analysis……………………………………………………………………………………….……..18

1.10.1 Java Example: Time Complexity of a Simple Loop…………………………………….….19

III
1.1 Introduction to Algorithm

Informally, an algorithm is a well-defined computational procedure that takes some input value
or set of values and produces an output value or set of values. In simple terms, an algorithm is a
sequence of steps that transforms the given input into the desired output. We can also think of an
algorithm as a tool used to solve a clearly defined computational problem. The problem
describes what relationship should exist between the input and output, while the algorithm
provides the exact steps needed to achieve that result. For example, sorting a sequence of
numbers into non decreasing order is a common computational problem. A sorting algorithm
takes a sequence such as ⟨ 31, 41, 59, 26, 41, 58⟩ and produces a reordered sequence like ⟨ 26,
31, 41, 41, 58, 59⟩ . Each such input sequence is an instance of the sorting problem, and sorting
is widely used because many programs rely on it as an intermediate step. There are many sorting
algorithms, and the best choice depends on factors such as the number of items, how sorted they
already are, restrictions on values, and the computer’s architecture or storage system. An
algorithm is considered correct if it halts and always produces the right output for every valid
input; otherwise, it is incorrect, though sometimes incorrect algorithms can still be useful if their
error rates are controlled. Generally Step-by-step procedure to solve a specific problem is an
algorithm.

Example:-Problem Statement

Write an algorithm to scan the phone's contact list.

Steps

1. Unlock your phone.

2. Open the Contacts app.

3. Start scanning the list.

4. Compare the contact name with the desired contact name.

5. If the names match, then match is found.

1
6. If the names do not match, then move to the next contact in the list.

1.2 Algorithm vs Program

 An algorithm is a step-by-step procedure to solve a specific problem.

 A program is also a step-by-step procedure to solve a specific problem.

So, what's the difference?

1. An algorithm is an abstract concept. Whereas, a program is a concrete implementation of the

algorithm.

Example:-

Algorithm

1. Start

2. Initialize a variable 'result' to 1.

3. Read the input number 'n'.

4. Repeat the following until 'n' becomes 0:

a. Multiply 'result' by 'n'.

b. Decrement 'n' by 1.

5. Print the value of 'result' as the factorial.

6. Stop.

2
Program

int fact(int n)

int result = 1;

while (n > 0) {

result = n;

n--;

return result;

2. An algorithm can be written in any language, while a program must be written using a
programming language only.

Algorithm

1. Start
2. Initialize a variable 'result' to 1.
3. Read the input number 'n'
4. Repeat the following until 'n' becomes O:

a. Multiply 'result' by 'n'.

b. Decrement 'n' by 1.

5. Print the value of 'result' as the factorial.

6. Stop.

3
Program

int fact(int n)

int result = 1;

while (n > 0) {

result = n;

{}}

n--;

return result;

3. An algorithm is developed during the design phase, and a program is developed during the
development phase.

4. An algorithm does not depend on the hardware and operating system while a program depends
upon them.

5. An algorithm is always analyzed, while a program is tested.

4
 Image 1:software Development Life Cycle

1.3 Properties of an algorithm

Finiteness: Algorithm must complete after a finite number of steps.

Definiteness: Each step must be clearly defined, having one and only one interpretation. At each
point in computation, one should be able to tell exactly what happens next.

Sequence: Each step must have a unique defined preceding and succeeding step. The first step
(start step) and last step (halt step) must be clearly noted.

Correctness: It must compute correct answer for all possible legal inputs.

Language Independence: It must not depend on any one programming language.

Completeness: It must solve the problem completely.

Effectiveness: It must be possible to perform each step exactly and in a finite amount of time.

Efficiency: It must solve with the least amount of computational resources such as time and
space.

5
1.4 Problems Solved by Algorithms

Algorithms are used to solve a wide variety of computational problems that appear in real-world
applications. Beyond sorting, algorithms play an essential role in fields such as biology,
networking, security, business, and engineering. For example, large scientific projects like the
Human Genome Project rely on algorithms to process DNA sequences efficiently. The Internet
depends on algorithms to determine optimal data routes and to make search engines retrieve
information quickly. Electronic commerce uses algorithms in cryptography to protect sensitive
information such as credit card numbers and passwords. Many industries use algorithms, such as
linear programming, to allocate limited resources in the most effective way. In addition,
algorithms help solve specific technical problems like finding the shortest path in a road map,
identifying the longest common subsequence between two sequences, generating a valid order of
interconnected parts in a system, or determining the convex hull of points in a plane. These
examples show that algorithms are fundamental tools for solving large, complex, and diverse
problems efficiently.

1.5 why Analyzing Algorithms?

Analyzing an algorithm means predicting how much of a computer’s resources it will use.
These resources may include Running time, memory, communication bandwidth, or even
specialized hardware. Among all these, the resource we measure most often is computational
time, because execution time usually determines how practical an algorithm is for real-world use.

When we have several possible algorithms to solve the same problem, analysis helps us
decide which one performs better. Sometimes more than one algorithm is efficient, but analysis
allows us to eliminate clearly inferior choices. This evaluation becomes increasingly important
as input sizes grow, because poor algorithms may become unusable at large scale.

Algorithm analysis is necessary primarily because it allows us to predict and guarantee

how an algorithm will perform, regardless of the specific machine or input variations.

6
Why We Analyze Running Time Instead of Using Clock-Time

Running time is considered the most important factor when evaluating an algorithm because,
in most computational problems, time is the most valuable resource. A program that takes too
long to finish becomes impractical, even if it uses reasonable memory or hardware.

However, using actual clock-time (the time measured by a stopwatch) is not a reliable or
consistent way to measure an algorithm’s efficiency. Real-world clock-time depends on many
external factors that can change from one run to another. These include:

Processor speed – Faster CPUs will complete tasks more quickly than slower ones.

Current processor load – If other programs are running, they may slow down execution.

Input size – Large inputs naturally take more time to process than small ones.

Input properties – Different types of input (sorted, random, repeated values, etc.) can affect
performance.

Operating environment – The operating system, memory state, or background services can
influence runtime.

Hardware configuration – Cache sizes, RAM speed, and storage type can affect execution.

Because of these variations, using actual time makes it impossible to compare algorithms fairly.

Mathematical Tools for Analysis

Analyzing algorithms even simple ones requires mathematics such as:

 Combinatory
 Probability theory
 Algebraic manipulation
 Identifying dominant terms in expressions

Because an algorithm may behave differently for different inputs, we need a standardized way to
describe its performance. This leads to simplified, widely accepted mathematical notations such
as Big-O, Big-Θ, and Big-Ω.

7
1.6 Order of Growth

When analyzing algorithms, our goal is not only to understand how they work but also how
their running time increases as the size of the input grows. To make this analysis manageable, we
apply several simplifications. First, instead of measuring the actual execution time of each line of
code, we represent these times using abstract constants such as c₁, c₂, and so on. Later, we
simplify further by combining these constants into expressions like an² + bn + c to describe total
running time. But this level of detail is often still more than we need.

To evaluate the true efficiency of an algorithm, we focus only on its order of growth, which
describes how the running time increases as the input size n becomes very large. This means we
pay attention only to the highest-degree term in the running-time expression, because lower-
degree terms become insignificant for large inputs. For example, in an expression like an² + bn +
c, the n² term dominates when n is large. Even the constant coefficient ‘a’ becomes unimportant
compared to the rapidly increasing effect of n² itself.

1.7 Asymptotic Notations

Asymptotic notation provides a mathematical framework to describe how functions behave as

their input grows large. In algorithm analysis, these notations are essential because they allow us
to express running times in a way that focuses on long-term growth trends rather than exact
execution times, which may vary across machines or specific inputs.

The functions we analyze—such as running-time functions—typically take natural numbers n

∈ {0, 1, 2 …} as their domain, because n represents the input size. However, in practice,
asymptotic notation is sometimes used more flexibly than its strict mathematical definition. For
convenience, we may extend these notations to real numbers or restrict them to specific ranges of
n.

Asymptotic Notation, Functions, and Algorithm Running Times

Asymptotic notation applies to functions, not directly to algorithms. But since an algorithm’s
running time can be expressed as a mathematical function—for example:

8
T (n) =an^2 +bn +c

We use asymptotic notation to describe the growth of this function. When we write: T (n) =Θ
(n^2)

We are simplifying the detailed expression into a form that captures only the essential growth
behavior. This hides constant factors (a, b, c) and lower-order terms, leaving only the dominant
term that determines growth for large n.

Although we frequently use asymptotic notation to describe running time, it can also be
applied to: Space usage, Number of memory accesses, Number of comparisons, any numeric
function, even those unrelated to algorithms.

Which Running Time Are We Describing?

When applying asymptotic notation to algorithms, it is important to understand which running

time we mean:

Worst-case running time: Most commonly used because it gives an upper bound and a
performance guarantee for all possible inputs.

Average-case running time: Used when inputs follow a known probability distribution.

Best-case running time: Rarely useful because it may not reflect real performance.

Sometimes, we are not analyzing just the worst-case behavior; instead, we want an asymptotic
description that applies to all inputs, regardless of whether they represent best, average, or worst
cases. Different asymptotic notations (O, Ω, and Θ) allow us to choose the kind of bound—upper,
lower, or tight—that suits the analysis goal.

9
There are Five Asymptotic Notations used to describe running time function:

Big-O notation — O (f (n))

Big-Ω notation — Ω (f (n))

Theta notation — Θ (f (n))

Little-o notation — o (f (n))

Little-ω notation — ω( f (n))

1.7.1 Θ-Notation (Theta Notation)

Θ-notation gives an asymptotically tight bound on a [Link] describes the exact order of
growth of an algorithm’s running [Link] describes functions that grow at the same rate up to
constant [Link]-order terms and constant coefficients are ignored.

Formal definition

For a function g (n), the set Θ (g (n)) is defined as:

Θ (g (n)) = {f (n)| there exist positive constants c1, c2, no such that

0≤ c1g (n) ≤ f (n) ≤c2g (n) for all n ≥ no}

Meaning:

A function f(n) belongs to Θ(g(n)) if:

For large enough n,f(n) always stays between c₁·g(n) (lower bound) and c₂·g(n) (upper
bound),where c₁, c₂, and n₀ are positive constants.

Example:

If running time = 5n^2+3n+7

10
→ The dominant term is

→ So running time = Θ (n²)

This is because lower-order terms become insignificant as n becomes large.

Why Θ-Notation Is Useful

 Gives exact growth rate

 Abstracts away machine differences (CPU speed, OS, data variations)
 Helps compare algorithms mathematically
 Shows true scalability for large inputs

Graph Intuition

Imagine three curves:

c₁·g(n) → lower boundary

c₂·g(n) → upper boundary

f(n) → must stay between them for n ≥ n₀

This means g(n) is an asymptotically tight bound for f(n).

Figure 1 Graphic example of Θ

11
1.7.2 Big-O Notation (O-notation)

O-notation gives an asymptotic upper bound on a function. It describes how fast a function
grows in the worst case.

Formal definition

For a function g (n):

Θ (g (n)) = {f (n)| there exist positive constants c, no such that

0≤f (n) ≤c g(n) for all n ≥ no}

Meaning

A function f (n) belongs to O (g (n)) if:

For large n

f (n) is always less than or equal to some constant multiple of g (n)

That constant is c

And the condition holds for all n ≥ n₀

Why Big-O is useful

Big-O allows us to:

Give a worst-case upper bound on running time

Analyze algorithms by looking at their loop structure

Ignore machine details and constant differences

Compare scalability of algorithms as input grows

12
Graph Intuition

Imagine: f (n) curve, c·g (n) curve (a scaled-up version of g(n))

For all n ≥ n₀: f (n) ≤c⋅ g (n)

So f(n) lies on or below the upper boundary c·g(n).

Figure 2: graphic example of O

Examples1: The following points are facts that you can use for Big-O problems:
1<=n for all n>=1
n<=n2 for all n>=1
2n<=n! for all n>=4
log2n<=n for all n>=2
n<=nlog2n for all n>=2
1. f (n) =10n+5 and g (n)=n. Show that f(n) is O(g(n)).
To show that f (n) is O (g (n)) we must show that constants c and k such that
f(n) <=c.g(n) for all n>=k
Or 10n+5<=c.n for all n>=k
Try c=15. Then we need to show that 10n+5<=15n
Solving for n we get: 5<5n or 1<=n.
So f(n) =10n+5 <=15.g(n) for all n>=1.
(c=15,k=1).

13
Example 2 f(n) = 3n2 +4n+1. Show that f(n)=O(n2).
4n <=4n2 for all n>=1 and 1<=n2 for all n>=1
3n2 +4n+1<=3n2+4n2+n2 for all n>=1
<=8n2 for all n>=1
So we have shown that f(n)<=8n2 for all n>=1
Therefore, f (n) is O(n2) (c=8,k=1)
Exercise:
f(n) = (3/2)n2+(5/2)n-3
Show that f(n)= O(n2)
In simple words, f (n) =O(g(n)) means that the growth rate of f(n) is less than or equal to
g(n).
1.7.3 Big-Omega (Ω) Notation

Just like Big-O notation gives an asymptotic upper bound on a function, Big-Omega (Ω) notation
gives an asymptotic lower bound. This is effectively the best-case lower bound.

Formal Definition

A function f(n) belongs to Ω(g(n)) if:

There exist positive constants c and n₀ such that: 0≤cg(n)≤f(n) for all n≥n

Interpretation:

For all values of n to the right of n₀ on the graph,

f (n) is on or above the line c·g(n).

So Ω (g (n)) gives a lower bound on how fast f (n) can grow.

Example: If f(n) =n2, then f(n)= Ω( n)

In simple terms, f(n)=Ω( g (n)) means that the growth rate of f(n) is greater that or equal to g(n).

14
Graphical represented

Figure 3: Graphic example of Ω

1.8 Comparing Worst-Case and Average-Case Analysis

When analyzing an algorithm's performance, we typically consider three main scenarios:

best-case, worst-case, and average-case. The two most practically important are worst-case and
average-case.

Algorithm complexity

Algorithm complexity measures how resources like time or memory grow as a problem gets
bigs. There are three main way to describe this those are worst-case, average-case and best-case
complexity. Understanding this helps to predict how an algorithm performs in different
situation .guiding better software choice and design.

Algorithm performance refers to how efficiently an algorithm use time and memory to solve the
problem when analysing an algorithm.

How much memory the algorithm use while running.

1.8.1 Worst case analysis

In the worst case analysis we calculate upper bound or running time as an algorithm. We must
know the case that cases maximum number of operation to be executed

15
For linear search the worst case happen when the element to be searched (is above the code) not
present in the array. When x is not present the search function compers it with all the element or
array [] One by one

Therefore the worst case time complexity of linear search would be o(n) Worst case happen the
element search in the array is not happen.

Example

Int array[] {1,10,30,15,70,21,121,87,23,101,187,222}

For searching 1 it take minimum time

For searching 222 .it take more time it will go to each element one by one.

Worst-case complexity gives maximum amount of resources. All algorithms might need, for
example, searching a value in all unsorted lists with linear search, in the worst case. You take
every item. So the complexity is O (n). This helps developers ensure their program will slow
down unexpectedly.

1.8.2 Average case analysis

Average case analysis calculates the expected time an algorithm takes over all possible inputs. It
assumes that all inputs are equally likely.

In Average Case Analysis, we take all possible inputs and calculate computing time for all inputs.
Sum all the calculated values and divide the sum by total number of inputs. We must now or
predict distribuion of cases for the linear search problem.

Let us assume that all cases are uniformly distributed. So we sum all the cases and divide the
sum (n+1) following is the value of Average Case Time Complexity.

1.8.3 Best case complexity

is the measure of the minimum amount of time an algorithm takes to run for an input of size n
under the most favorable or ideal conditions.

In best case analysis, we calculate lower bound or running time of an algorithm. We must know
the case that case, minimum number of operations to be executed in linear search problem, the

16
best case occurs when x is present at the first location. The number of operations in best case is
constant (not dependent on n).So time complexity in the best case would be O (n).

Why best case is important.

 Helps understand the lower limits of performance.

 Show how fast the algorithm can be when everything goes perfect.
Which one to use?

Most of the time, we do worst-case analysis to analyze algorithms. In the worst analysis, we
guarantee an upper bound on the running time of algorithms. Which is good information.

The average case analysis is not easy to do in most of the Practical cases and it is really done. In
average case analysis, we must know or predict mathematics distribution of all possible inputs

The best case analysis is bogus. granting a lower bound on an algorithm doesn't provide any
information as the worst case an algorithm may take years for run.

1.9 Time vs. Space Trade-Offs

Is the balance between how fast a program runs, which is called time complexity, and how much
memory it uses, which is called space complexity. Algorithm design often involves a trade-off
between the two main resources:

Algorithm design often involves a trade-off between the two main resources:

 Time Complexity: - is a fundamental concept in algorithm analysis that measures the

amount of time required by an algorithm to run as the input size increases.

A lower time complexity is desired to improve speed, but it may require more space or memory

 Space Complexity: - is the amount of memory or space required by an algorithm to solve

a problem as the input size increases.

A lower space complexity is desired to conserve memory, but it could slow down the program.

17
In computer engineering we often cannot optimize both speed and memory at the same time. If
we want our program to run faster, we usually need to use more memory. If we want to reduce
memory usage, the program often becomes slower. This is why it is called a “trade-off” — we
trade time for space or space for time.

 Example Consider the problem of calculating Fibonacci numbers (means the sum of the
two preceding ones).

If we use a simple recursive method that does not store previous results, the computer repeats the
same calculations many times. This method uses very little memory, but it is very slow because
of repeated work. On the other hand, if we use a method called dynamic programming, we store
the results of previous calculations in an array. This uses more memory, but the program
becomes much faster because it avoids precomputation. This is an example of using more space
to save time.

 Example file compression

When we compress a file, we reduce its size so that it uses less storage space and can be sent
faster over a network. However, the computer needs extra processing time to compress and
decompress the file. In this case, we are saving space but spending more time.

In real-world applications, engineers must decide what is more important: speed or memory. For
example, in small devices like smartphones or embedded systems, memory is limited, so saving
space is more important.

In real-time systems such as medical devices or air traffic control systems, speed is crucial, so
designers are willing to use more memory to make the system faster.

1.10 Complexity Analysis

Complexity Analysis is the systematic study of the resources required for an algorithm to run.
These resources are generally measured in two primary ways:

Time – how long the algorithm takes to execute

18
Space – how much memory the algorithm uses

The purpose of complexity analysis is to provide a platform-independent way of comparing

algorithms. Instead of depending on CPU speed, RAM size, programming language, or compiler
efficiency, we analyze the mathematical growth of the algorithm as the input size n increases.
This allows us to judge which algorithm will perform better for large inputs.

1.10.1 Java Example: Time Complexity of a Simple Loop for liner time O (n)

public class SimpleLoopExample {

public static void main(String[ ] args) {

int n = 10;

for (int i = 0; i < n; i++) {

[Link](i);

Time Complexity Analysis

Step-by-Step Explanation

1. The loop runs from

i = 0 to i = n-1.

2. That means the loop executes n-1 times.

19
3. Inside the loop, the statement

[Link] (i);

Takes constant time, written as O (1).

Total Time Complexity

We multiply:

Number of iterations → n

Time per iteration → O(1)

So the total time:T(n)=n×0(1)=o(n)

Java Example: O(1) Time Complexity for constant

public class Main {

public static void main(String[] args) {

int[] arr = {5, 10, 15, 20};

// Accessing an element using index

[Link](arr[2]);

Accessing an array element by index (arr[2]) takes constant time

time complexity = O(1)

20
21