Introduction to Data Structures
and Algorithms
1
Algorithm
• Method of solving a problem
• An algorithm must have:
• Input – Supplied information
• Output – Result received
• Finiteness – Must have a terminating point
• Definiteness – Steps should be clear & unambiguous
• Effectiveness – No application of intelligence to perform
steps
• A sequence of instructions that act on some input
to produce some output in a finite number of
definite steps.
2
• Two ways to solve repetitive code
• Iterative (Repetitive)- Uses Loops
• Recursive –Uses divide and conquer
3
Time and Space Complexity
4
Deepa Krishnan
Complexity
• Time complexity
• Amount of computer time needed for a task unit
to run to completion
• important for the programs which interact with
user
• Very important for real time systems
• Space complexity
• Amount of memory a program needs to run to
its completion
• Very important aspect to consider if the code is
running on devices with small memory
5
Space Complexity
Adding array elements iteratively
int addIt(int array[], int size){
int i, sum=0;
for(i=0;i<size;i++)
sum+=array[i];
return sum;}
Adding array elements recursively
int addRe(int array[], int size){
if(size<0) return 0;
else
return addRe(array, size -1) + a[size];
}
6
Stack space
• Iterative function:
• size * sizeof(array elements)+ sizeof(size) +sizeof(i) +
sizeof(sum)
• 10*4+4+4+4=52
• Recursion function
• Depth of the recursion=size+1.
• (size+1)*(size * sizeof(array elements)+ sizeof(size))
• 11*(10*4+4)= 484
7
Time complexity
• Execution time depends on the nature of the program
statement.
• Program step: Execution time of a statement that is
independent of instance characteristic. For instance:
x=y/z and x=1 both have program step of 1 though
execution time will strictly depend on the time for divide
also in x=y/z.
• Declarative statement: Program step count is 0 except
declaration with initialization takes execution time 1.
• Expression and assignment statement: 1 except the
expression that involve function calls
• If statement: 1+ Program step count for if-part
statements+ Program step count for else-part
statement 8
Time complexity
• Iterative statements: if k is number of loops
• Program step count for while loop:
• k* steps for conditional statement+ k* program steps
of statement inside the body
• Program steps for do-while loop:
• (k+1)* steps for conditional statement+ k* steps of
statement inside the body
• Program steps for for loop:
• steps for expression1+(k+1) * steps of condition+ k*
steps of statement inside the body+ k* steps for
expression2 9
Time complexity
• Switch statement: Calculated same as that for the if-
statement. Some compilers may use a completely
different way to implement switch-case table with case
expression with addresses of the corresponding
statements.
• Function invocation: Program step count is 1
• Function return: return statement that returns a value has
program step of 1, otherwise 0.
• Control transfer: break, continue, go to have program
steps is 1
• Example: Program steps for addRe():
• 3 + program steps for addRe(n-1)
= 6 + program steps for addRe(n-2)
…
= 3n + program steps for addRe(0)
= 3n +2, n>=0
10
Big-Oh
• The main issue concerning execution speed is the
size of the input. For small size of input the
difference in execution speed is almost negligible.
Therefore performance is measured for larger input
size.
• Mathematical definition of Big-Oh:
• f(n)=O(g(n)) if there exist +ve constant c and n0
such that f(n)<=c g(n)
• 3n+2=O(n) 3n+2<=4n for all n>=2.
• An algorithm that runs in O(n2) time indicates that
execution time increases with the square of the input
size. ‘n’ in O(n2) indicates the input size .For
example, if we increase input size by a factor of ten,
execution time will increase by a factor of 100. 11
Data Structures
• Way in which the data is organised
• Need for Data Structures
• Maintain data easily
• Choosing a correct Data Structure improves
algorithm efficiency
12
Types of Data Structures
• Linear (Sequential)
• Arrays
• Linked Lists
• Stacks
• Queues
• Non-Linear
• Trees
• Graphs
• Hash Tables
13