1

BBIT 2.2
Jomo kenyatta university of agriculture and technology

Data structures and algorithms

LECTURE 1
Introduction, efficiency and complexity
Definition
An algorithm for a particular task can be defined as “a finite sequence of instructions,
each of which has a clear meaning and can be performed with a finite amount of effort in
a finite length of time”. As such, an algorithm must be precise enough to be understood
by human beings.
However, in order to be executed by a computer, we will generally need a program
It is also worth bearing in mind the distinction between different programming
paradigms: Imperative Programming describes computation in terms of
instructions that change the program/data state, whereas Declarative Programming
specifies what the program should accomplish without describing how to do it.
Fundamental questions about algorithms Given an algorithm to solve a particular
problem, we are naturally led to ask:
1. What is it supposed to do?
2. Does it really do what it is supposed to do?
3. How efficiently does it do it?
The technical terms normally used for these three aspects are:
1. Specification.
2. Verification.
3. Performance analysis.
The specification should formalize the crucial details of the problem that the algorithm
is intended to solve. Sometimes that will be based on a particular representation of the
associated data, and sometimes it will be presented more abstractly. Typically, it will
have to specify how the inputs and outputs of the algorithm are related, though there is
no general requirement that the specification is complete or non-ambiguous.
For more complicated specifications and/or algorithms, the fact that an algorithm
satisfies its specification may not be obvious at all. In this case, we need to spend some
effort verifying whether the algorithm is indeed correct.
 2

The efficiency or performance of an algorithm relates to the resources required by it,

such as how quickly it will run, or how much computer memory it will use.
The term data structure is used to denote a particular way of organizing data for
particular types of operation.
Data types such as int, float, double, long, etc. are considered to be in-built data types
and we can perform basic operations with them such as addition, subtraction, division,
multiplication, etc. Now there might be a situation when we need operations for our
user-defined data type which have to be defined. These operations can be defined only
as and when we require them. So, in order to simplify the process of solving problems,
we can create data structures along with their operations, and such data structures that
are not in-built are known as Abstract Data Type (ADT).
Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a
set of values and a set of operations. The definition of ADT only mentions what
operations are to be performed but not how these operations will be implemented.
Will look at numerous data structures ranging from familiar arrays and lists to more
complex structures such as trees, heaps and graphs, and we will see how their
choice affects the efficiency of the algorithms based upon them.
At an even higher level of abstraction are design patterns which describe the design of
algorithms, rather the design of data structures. These embody and generalize
important design concepts that appear repeatedly in many problem contexts. They
provide a general structure for algorithms, leaving the details to be added as required for
particular problems. These can speed up the development of algorithms by providing
familiar proven algorithm structures that can be applied straightforwardly to new
problems.
We shall learn how to develop and analyse increasingly efficient algorithms for
manipulating and performing useful operations on those structures, and look in detail at
developing efficient processes for data storing, sorting, searching and analysis.
Data is ultimately stored in computers as patterns of bits, though these days most
programming languages deal with higher level objects, such as characters, integers, and
floating-point numbers. Generally, we need to build algorithms that manipulate
collections of such objects, so we need procedures for storing and sequentially
processing them.
Arrays In computer science, the obvious way to store an ordered collection of items is as
an array. Array items are typically stored in a sequence of computer memory locations,
but to discuss them, we need a convenient way to write them down on paper. We can
just write the items in order, separated by commas and enclosed by square brackets.
 3

Thus, [1, 4, 17, 3, 90, 79, 4, 6, 81] is an example of an array of integers.

If we call this array a, we can write it as: a = [1, 4, 17, 3, 90, 79, 4, 6, 81]
This array a, has 9 items, and hence we say that its size is 9.
In everyday life, we usually start counting from 1. When we work with arrays in
computer science, however, we more often (though not always) start from 0. Thus, for
our array a, its positions are 0, 1, 2, . . . , 7, 8. The element in the 8th position is 81, and
we use the notation a[8] to denote this element. More generally, for any integer i
denoting a position, we write a[i] to denote the element in the i th position. This position
i is called an index (and the plural is indices). Then, in the above example, a[0] = 1, a[1]
= 4, a[2] = 17, and so on.
We say that the individual items a[i] in the array a are accessed using their index i, and
one can move sequentially through the array by incrementing or decrementing that
index, or jump straight to a particular item given its index value. Algorithms that
process data stored as arrays will typically need to systematically visit all the items in the
array, and apply appropriate operations on them.
Dynamic and static arrays

A dynamic array is an array that can be changed in size after it is created. A static array
is an array whose size is set when it is created and cannot be changed.

Dynamic arrays are often used because they can be changed as needed, which can be
helpful when the size of the data set is unknown or may change over time. Static arrays
are often used when the size of the data set is known in advance and will not change.

Both dynamic and static arrays have their advantages and disadvantages. Dynamic
arrays are more flexible, but they can be more difficult to manage. Static arrays are
easier to manage, but they are not as flexible.

It is important to choose the right type of array for the task at hand. If the size of the
data set is known in advance and will not change, then a static array may be the best
choice. If the size of the data set is unknown or may change over time, then a dynamic
array may be the best choice.

Loops and Iteration

The standard approach in most programming languages for repeating a process a
certain number of times, such as moving sequentially through an array to perform the
same operations on each item, involves a loop.
 4

Invariants
An invariant, as the name suggests, is a condition that does not change during execution
of a given program or algorithm. It may be a simple inequality, such as “i < 20”, or
something more abstract, such as “the items in the array are sorted”.
Invariants are important for data structures and algorithms because they enable
correctness proofs and verification. In particular, a loop-invariant is a condition that is
true at the beginning and end of every iteration of the given loop.
We will also see how invariants (sometimes called inductive assertions) can be used
to formulate similar correctness proofs concerning properties of data structures that are
defined inductively.
Efficiency and Complexity
We talk about the time complexity of the algorithm as an indicator of how the execution
time depends on the size of the data structure.
Here we talk about the space complexity as how the memory requirement depends on
the size of the data structure.
Worst versus average complexity
Another thing that has to be decided when making efficiency considerations is whether
it is the average case performance of an algorithm/program that is important, or
whether it is more important to guarantee that even in the worst case the performance
obeys certain rules. For many applications, the average case is more important, because
saving time overall is usually more important than guaranteeing good behaviour in the
worst case. However, for time-critical problems, such as keeping track of aeroplanes in
certain sectors of air space, it may be totally unacceptable for the software to take too
long if the worst case arises.
Big-O notation for complexity class
Very often, we are not interested in the actual function C(n) that describes the time
complexity of an algorithm in terms of the problem size n, but just its complexity class.
This ignores any constant overheads and small constant factors, and just tells us about
the principal growth.
Big O notation (with a capital letter O, not a zero), also called Landau's symbol, is a
symbolism used in complexity theory, computer science, and mathematics to describe
the asymptotic behavior of functions. Basically, it tells you how fast a function grows or
declines. Landau's symbol comes from the name of the German number theoretician
Edmund Landau who invented the notation. The letter O is used because the rate of
growth of a function is also called its order. For example, when analyzing some
 5

algorithm, one might find that the time (or the number of steps) it takes to complete a
problem of size n is given by T(n) = 4 n 2 - 2 n + 2. If we ignore constants (which makes
sense because those depend on the particular hardware the program is run on) and
slower growing terms, we could say "T(n) grows at the order of n 2 " and write (n) = O(n 2
).
Here is a list of classes of functions that are commonly encountered when analyzing
algorithms. The slower growing functions are listed first. c is some arbitrary constant.
1. O(1) constant
2. O(log(n)) logarithmic
3. O(nlog(n)) n logarithmic of n
4. O(n) linear
5. O (n 2 ) quadratic
6. O(n c ) polynomial
7. O(c n ) exponential