Examples for Computing Time & Space Complexity

Ex. 1:
Find the result of ??
n
j
j A
1
This problem is characterized with n
Space Complexity: This algorithm requires two cells , for S and j
variables , this is constant storage and independent with problem
characteristics, thus
S sum (n)= 0
Time Complexity with Operation counts: With selection addition
operation for array elements (A)
T sum (n)=n
Time Complexity with Step counts:
Ex. 2: Find the summation of the elements of two array:
C(mn) = A(mn) + B(mn)
2
This problem is characterized with m and n
Space Complexity:
Sadd
(m,n) =mn + 2 (where mn is array size, 2 for i, j).
Time Complexity with Operation counts: With selection addition
operation between the elements of (A), (B) arrays
Tadd (m,n) = mn
Time Complexity with Step counts:
Note:
This expression is accepted when n>=m, but when m>n , two for
statements are replaced to decrease time complexity , it becomes:
H.W. :
Compute space and time complexity of a problem which finds the
summation of the elements of two array:
Z(n) = X(n) + Y(n)
Ex. 3: Fibonacci Numbers.
It is starting as:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …………
Where as every new number will be getting through adding two previous
numbers, if first number in Fibonacci is F0, then F0=0 and F1=1, in
general: Fn = Fn-1 + Fn-2 , n>=2 .
3
This problem is characterized with n.
Space Complexity: This algorithm requires four cells , for storing the
values of fib, fnm1, fnm2 and i, this is constant storage and independent
with problem characteristics, thus
Sfibonacci(n) = 0
Time Complexity with Operation counts: With selection assignment
operation between the elements of Fibonacci numbers:
Time Complexity with Step counts:
Two cases must be considered in this method:
First case : when n=0 or n=1, number of steps is 3.
Second case : when n>1, number of steps is 4n+1.
There is a relationship between time complexity and problem s
characteristics, where as increasing n leads to linear increasing in time
complexity, which is better than squared increasing.
Note:
In most problems there is a balance between amount of time and
algorithm s space, more storage leads to increase running speed, and the
reverse of this statement is true.
Ex. 4: Reform Fibonacci algorithm.
Space Complexity:
Time Complexity with Step counts: