Outline
• Asymptotic analysis
• Array
• Pointers
• Structures
• Stack
May 5, 2021
1
Asymptotic Analysis
• In order to choose the best algorithm for a particular
task, we need to be able to judge how long a
particular solution will take to run.
• Need to compare algorithms against one another.
May 5, 2021 2
• This is why we need to analyze an algorithm.
• To analyze an algorithm is to determine the amount
of resources (e.g. time and storage) necessary to
execute it.
• Most algorithms are designed to work with inputs of
arbitrary length.
May 5, 2021 3
• Usually the efficiency or complexity of an algorithm
is stated as a function relating the input length to the
number of steps (time complexity) or storage
locations (space or memory complexity) required to
execute the algorithm.
May 5, 2021 4
• To estimate the complexity function for large length
of input is vital.
• It's also easier to predict bounds for the algorithm
than it is to predict an exact speed.
May 5, 2021 5
• Asymptotic notation is a shorthand way to
write down and talk about 'fastest possible'
and 'slowest possible' running times for an
algorithm.
• Big O notation, omega notation and theta
notation are used to this end.
May 5, 2021 6
Big-Oh Notation
• Big O notation is a mathematical notation used to
describe the asymptotic behavior of functions.
• Its purpose is to characterize a function's behavior
for large inputs in a simple but rigorous way that
enables comparison to other functions.
May 5, 2021 7
Definition [Big-Oh]
• The function f(n) = O(g(n)) (read as “f of n is big oh of
g of n”) iff(read as “if and only if”) there exist positive
constants c and n0 such that f(n)≤ c.g(n) for all n,
n≥n0.
• Upper bound on a function
May 5, 2021 8
• Using O notation, we can describe the running time
of an algorithm by inspecting the algorithm’s overall
structure.
• It is important to understand that the actual running
time depends on the particular input of size n.
May 5, 2021 9
• “The running time is O(n2)” is that the worst-case
running time (which is the function of n) is O(n2), or
no matter what particular input of size n is chosen
for each value of n, the running time on that set of
inputs is O(n2).
May 5, 2021 10
• Some of the typical complexities (computing time)
represented by big-oh notation are:
1. O(1) Constant
2. O(n) Linear
3. O(n2) Quadratic
4. O(n3) Cubic
5. O(2n) Exponential
6. O(logn) Logarithmic
May 5, 2021 11
Example
Derive the big-oh notation, if f(n)= 8n+7 and
g(n)=n
Solution: To show f(n) is O(g(n)), we must
consider positive constants C and integer n0,
such that f(n) ≤ Cg(n) for all n> n0
Let C= 15
Now, we must show that 8n+7 ≤ 15n
Or 7 ≤ 7n or 1 ≤ n
May 5, 2021 12
Therefore,
f(n)= 8n+7 ≤ 15n for all n ≥ 1,
Where C=15 and n0=1.
Hence, f(n)=O(g(n).
May 5, 2021 13
Omega Notation
• Omega notation provides an asymptotic lower
bound.
• When we use it to bind the best-case running time of
an algorithm, by implication we also bound the
running time of the algorithm on arbitrary inputs as
well.
May 5, 2021 14
Definition
• The function f(n) = Ω(g(n)) (read as “f of n is omega
of g of n”) iff(read as “if and only if”) there exist
positive constants c and n0 such that f(n)≥ c.g(n) for
all n, n≥n0.
May 5, 2021 15
Example
Deduce the omega notation of f(n)= 2n+6 and
g(n)=2n.
Given, f(n)=2n+6 and g(n)=2n
For n=0,
f(n)= 2(0)+6= 6
g(n)= 2(0)=0
i.e., f(n)> g(n)
For n=1,
May 5, 2021 16
f(n)= 2(1)+6
= 2+6= 8
g(n)= 2(1)=2
i.e., f(n)>g(n)
Therefore, we can say that,
f(n) > Cg(n), for n > 1
May 5, 2021 17
Theta Notation
• Used when the function ‘f’ can be bounded both
from above and below by the same function g.
May 5, 2021 18
• Definition: The function f(n) =θ (g(n)) (read as “f of n
is theta of g of n”) iff(read as “if and only if”) there
exist positive constants c1, c2 and n0 such that
c1.g(n)≤f(n≤c2.g(n) for all n, n≥n0.
May 5, 2021 19
• When write f(n) = θ(g(n)), then ‘f’ lies between c1
times the function g and c2 times the function g
except possibly when n is smaller than n0.
May 5, 2021 20
• Here c1 and c2 are positive constants. Thus g is both a
lower and upper bound on the value of ‘f’ for
suitably large n.
• Another way to view the theta notation is that it
says f(n) is both Ω(g(n)) and O(g(n)).
May 5, 2021 21
Example
Deduce the theta notation if f(n)= 2n+8
Let f(n)= 2n+8 > 5n where n≥ 2
Similarly, f(n)= 2n+8 > 6n where n ≥ 2
and f(n)= 2n+8 < 7n, for n ≥ 2
Thus, 5n < 2n+8 < 7n, for n ≥ 2,
Hence, C1=5 and C2=7
Hence, f(n)=2n+8= θ(n)
May 5, 2021 22
Modularity
• To simplify the programs, the concept of modularity
was introduced.
• Modularity is dividing the larger problems to sub
problems.
• The modularity of most systems can be represented
by hierarchical structure.
May 5, 2021 23
May 5, 2021 24
• Single main module at level gives a brief general
description of the problem.
• Main module is sub-divided into sub modules at level
2 that gives detailed description.
• The modules at level 2 are further sub divided as
modules at level 3, and so on.
May 5, 2021 25
• First problem: Logical relationship between the data
elements in the problem.
• Understand the data itself.
• Data consist of a set of items or atoms.
• Data consists of single element such as integers, bits,
character or set of such items.
May 5, 2021 26
• Second problem: to decide on operations which
must be performed on the data structures.
• Operations: create or destroy operation OR insert
and delete
• Third problem: representation of a data structure in
the memory
May 5, 2021 27
• The representation of data structures in memory is
called a storage structure.
• Array is storage structures for a data structure
May 5, 2021 28
• Data structure can be stored both in main and the
auxiliary memory
• A storage structure representation in auxiliary
memory is often called as file structure.
May 5, 2021 29
• Fourth problem: selection of a programming
language
• The programming language chosen for the
implementation of an algorithm should posses the
particular representation chosen for the data
structures in the problem being solved.
May 5, 2021 30
Arrays
• Collection of data elements that are of the same type
(e.g., integers and characters).
• Stores the different elements at consecutive
memory locations.
• Can be used as a pointer to the first array
element.
May 5, 2021 31
• Linear array (one dimensional array) is the simplest
type of data structures.
• Linear array means a list of a finite number n of
similar data type referenced respectively by a set of n
consecutive numbers 1, 2, 3… n.
May 5, 2021 32
• Example: if the name of the array is A then the
elements of array A are denoted either by subscript
notation, or by the parenthesis notation, or by the
bracket notation.
May 5, 2021 33
a1, a2, a3… an
or
A (1), A (2), A (3)… A (N)
or
A [1], A [2], A [3]… A [N]
• Where the number N in A (N) is called a subscript
and A [N] is called a subscripted variable.
May 5, 2021 34
double[] myList = new double[10];
myList reference myList[0]
myList[1]
myList[2]
myList[3] An Array of 10 Elements
myList[4]
of type double
myList[5]
myList[6]
myList[7]
myList[8]
myList[9]
May 5, 2021 35
Array Applications
• Given a list of test scores, determine the maximum
and minimum scores.
• Read in a list of student names and rearrange them
in alphabetical order (sorting).
• Given the height measurements of students in a
class, output the names of those students who are
taller than average.
May 5, 2021 36
• Syntax:
<type> <arrayName>[<array_size>]
Ex. int Ar[10];
• The array elements are all values of the type <type>.
• The size of the array is indicated by <array_size>,
the number of elements in the array.
• <array_size> must be an int constant or a
constant expression. Note that an array can have
multiple dimensions.
May 5, 2021 37
Subscripting
• Declare an array of 10 integers:
int Ar[10]; // array of 10 ints
• To access an individual element we must apply a subscript to
array named Ar.
– A subscript is a bracketed expression.
• The expression in the brackets is known as the index.
– First element of array has index 0.
Ar[0]
– Second element of array has index 1, and so on.
Ar[1], Ar[2], Ar[3],…
– Last element has an index one less than the size of the array.
Ar[9]
• Incorrect indexing is a common error.
May 5, 2021 38
Subscripting Example
//For loop to fill & print a 10-int array
#include <iostream>
using namespace std;
int main ( ) {
int index, ar[10]; // array for 10 integers
// Read in 10 elements.
cout << "Enter 10 integers: ";
for(index = 0; index < 10; index ++)
cin >> ar[index];
cout << endl;
cout << "The integers are ";
for(index = 0; index < 10; index ++)
cout << ar[index] << " ";
cout << endl;
return 0;
}
May 5, 2021 39
Sorting with Arrays: Example
// Compare and sort three integers
void swap (int&, int&);
int main ( ) {
int ar[3]; // input integers
// Read in three elements.
cout << "Enter three integers: ";
cin >> ar[0] >> ar[1] >> ar[2];
if (ar[0] > ar[1]) swap (ar[0], ar[1]);
if (ar[1] > ar[2]) swap (ar[1], ar[2]);
if (ar[0] > ar[1]) swap (ar[0], ar[1]);
cout << "The sorted integers are " << ar[0]
<<", " << ar[1] << ", " << ar[2]
<< endl;
return 0;
}
May 5, 2021 40
Program with Arrays
int main()
{
int values[5]= {11,1,3,6,10};
for (int i = 1; i < 5; i++)
{
values[i] = values[i] + values[i-1];
}
values[0] = values[1] + values[4];
}
May 5, 2021 41
Copying Arrays
Using a loop:
int[] sourceArray = {2, 3, 1, 5, 10};
int[] targetArray = new int[[Link]];
for (int i = 0; i < [Link]; i++)
targetArray[i] = sourceArray[i];
May 5, 2021 42
Multidimensional Arrays
Declaring Variables of Multidimensional Arrays and Creating
Multidimensional Arrays
int[][] matrix = new int[10][10];
or
int matrix[][] = new int[10][10];
matrix[0][0] = 3;
for (int i=0; i<[Link]; i++)
for (int j=0; j<matrix[i].length; j++)
{
matrix[i][j] = (int)([Link]()*1000);
}
double[][] x;
May 5, 2021 43
Pointers
• A pointer is anything that tells us where something
can be found.
– Addresses in the phone book
– URLs for webpages
– Road signs
• Pointer is a variable storing an address.
May 5, 2021 44
• In C,
– A pointer can contain the memory address of any
variable type
– A primitive (int, char, float)
– An array
– A union
– Dynamically allocated memory
– Another pointer
– A function
– There’s a lot of syntax required to create and use
pointers
May 5, 2021 45
Use of pointers
• They allow to refer to large data structures in a
compact way.
• Sharing between different parts of programs.
• They make it possible to get new memory.
• They make it easy to represent relationships among
data items.
May 5, 2021 46
C Pointer Variables
To declare a pointer variable, we must do two
things
– Use the “*” (star) character to indicate that the
variable being defined is a pointer type.
– Indicate the type of variable to which the pointer will
point (the pointee). This is necessary because C
provides operations on pointers (e.g., *, ++, etc)
whose meaning depends on the type of the pointee.
• General declaration of a pointer
type *name of Pointer;
May 5, 2021 47
Pointer Operators
The two primary operators used with pointers are
* (star) and & (ampersand)
– The * operator is used to define pointer variables
and to deference a pointer. “Dereferencing” a
pointer means to use the value of the pointee.
– The & operator gives the address of a variable.
Recall the use of & in scanf( )
May 5, 2021 48
Pointer examples
int x = 1, y = 2, z[10];
int *ip; /* ip is a pointer to an int */
ip = &x; /* ip points to (contains the memory address of) x */
y = *ip; /* y is now 1, indirectly copied from x using ip */
*ip = 0; /* x is now 0 */
ip = &z[5]; /* ip now points to z[5] */
If ip points to x, then *ip can be used anywhere x can be
used so in this example *ip = *ip + 10; and x = x + 10;
are equivalent.
May 5, 2021 49
The * and & operators bind more tightly than arithmetic
operators so
y = *ip + 1; takes the value of the variable to which ip
points, adds 1 and assigns it to y
• Similarly, the statements *ip += 1; and ++*ip; and
(*ip)++; all increment the variable to which ip points.
(Note that the parenthesis are necessary in the last
statement; without them, the expression would
increment ip rather than what it points to since
operators like * and ++ associate from right to left.)
May 5, 2021 50
Pointer Arithmetic and Array
May 5, 2021 51
May 5, 2021 52
May 5, 2021 53
• Pros
– Efficiency
– Convenience
• Cons
– Error-prone
– Difficult to debug
May 5, 2021 54
Structures
• A Structure is a collection of related data items,
possibly of different types.
• A structure type in C++ is called struct.
• Structures hold data that belong together.
May 5, 2021 55
• Examples:
– Student record: student id, name, major, gender,
start year, …
– Bank account: account number, name, currency,
balance, …
– Address book: name, address, telephone number,
…
May 5, 2021 56
• In database applications, structures are called
records.
• Individual components of a struct type are called
members (or fields).
• Members can be of different types (simple, array or
struct).
May 5, 2021 57
• Syntax of the structure type:
typedef struct{
type1 id1;
type2 id2;
…
} struct_type;
• E.g.,
typedef struct{
char[20] name;
int age;
} student_info;
May 5, 2021 58
• Declaration:
student_info student1,
student2 = {“Wang”, 18};
• A hierarchical structure is a structure containing
components which are also structures.
typedef struct{
int NumOfStudents;
student_info students[20];
} class_info;
May 5, 2021 59
• We can reference a component of a structure by the
direct component selection operator, which is a
period.
• E.g.,
strcpy([Link]);
[Link] = 18;
printf(“%s is in age %d\n”, [Link],
[Link]);
May 5, 2021 60
• Suppose there is a structure defined as follows.
• typedef struct{
char name[20];
double diameter;
int moons;
double orbit_time,
rotation_time;
} planet_t;
May 5, 2021 61
• When a structure variable is passed as an input
argument to a function, all its component values are
copied into the local structure variable.
May 5, 2021 62
May 5, 2021 63
May 5, 2021 64
Arrays of Structures
• We can also declare an array of structures.
• E.g.,
typedef strucut{
int id;
double gpa;
} student_t;
• Usage:
student_t stulist[50];
stulist[3].id = 92922023;
stulist[3].gpa = 3.0;
May 5, 2021 65