A problem related to python, there might be a similar problem completed on the w

Question

A problem related to python, there might be a similar problem completed on the website but please help me with an original answer and not a copied one.

1) Consider the following pseudocode algorithms and give tight upper bounds to their complexity. Justify your answers

a) read n, where n is a nonnegative integer number

for i = 1to n do: print i

end for

b) read s, where s is a string of symbols

set k to the length of s

set times to 2k

for i = 1 to times do: print i

end for

c) Assume that di, where 0 i n, is a single symbol.

read n, where n is a nonnegative integer number

for i = 1 to n do: read di

end for

for i = 1 to n do: print di

end for

Explanation / Answer

a)
read n, where n is a nonnegative integer number
for i = 1to n do: print i
end for

Upper bound complexity will be O(n)
explanation:
as it is for loop and looping through 1 to n so it need to visit
from 1 to n so max time required O(n)

b)
read s, where s is a string of symbols
set k to the length of s
set times to 2k
for i = 1 to times do: print i
end for

Upper bound complexity will be O(n+n)

where n is the length of string.
explanation:
as times is the twice of k and k is length of string.
so it will loop through times and print i
so exactly k + k times run.

c)
Assume that di, where 0 i n, is a single symbol.
read n, where n is a nonnegative integer number
for i = 1 to n do: read di
end for
for i = 1 to n do: print di
end for

Upper bound complexity will be O(n+n)

it is same as the above except two for loops but it will loop exactly two times to 1...to ..n
so O(n+n) will the max time complexity to run

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.