Question

_{Calculate the space required by the below programs:}

_a-

n = len(S) # S has 15 numbers

j = 0

while j < n:

if S[j] == val:

return j # a match was found at index j

j += 1

b-

n = len(S)

total = 0

for j in range(n): # loop from 0 to n-1

for k in range(1+j): # loop from 0 to j

total += S[k]

return total

c-

data=[15,14,8,12,4]

big = data[0]

for val in data:

if val > big

big = val

return big

Answer 1

SPACE COMPLEXITY

The space that is required to process an algorithm for an input N

(OR)

The magnitude of auxiliary space your program takes to process the input N.

CALCULATION OF SPACE

Declaring an array of size n would add to the space complexity by a factor of O(n), a 2D array would add to the space complexity by a factor of O(n^2)

Variables add a space complexity of O(1) since the size of a particular datatype is always constant.

Note: User defined datatypes varies in size.

_A)

n = len(S) # S has 15 numbers

j = 0

while j < n:

if S[j] == val:

return j # a match was found at index j

j += 1

Space Required for this is Algorithm is O(n) where n is size of array S

Time required is O(n) of worst case (val is not found in array S)

B)

n = len(S)

total = 0

for j in range(n): # loop from 0 to n-1

for k in range(1+j): # loop from 0 to j

total += S[k]

return total

Space Required for this is Algorithm is O(n) where n is size of array S

S is the only array that requires space

total is variable of constant size

Generally O(n) + 1(total)

we omit constants so O(n) is space complexity

Time complexity is n*n ->O(n² ) because there is nested loop(2)

C)

data=[15,14,8,12,4]

big = data[0]

for val in data:

if val > big

big = val

return big

Space Required for this is Algorithm is O(n) where n is size of array data

big is the variable which has constant space.

generally O(n)+1(big)

we omit constants so O(n) is the space required

Time complexity is O(n) where n is no of elements we traverse

It is said to be worst case because we traverse each and every element in the array to compare with element big.

Thank You

please give a thumbs up if it is helpful....