In: Computer Science
Consider the three following pieces of pseudocodes. In each case,
- Give the number of times "Hello" will be printed,
- Generalize, giving the number of times as a function of n
- Express this in theta notation in terms of n.
a) set n = 32
set i = 1
while i<= n
print "Hello"
i=i*2
endwhile
b) set n = 4
set i = 1
while i not equal to n
print "Hello"
i=i+2
endwhile
c) set n = 4
set i = 1
while i<= n
set j = 1
while j <= i
print "Hello"
j=j+1
endwhile
i=i+1
endwhile
a) set n = 32
set i = 1
while i<= n
print "Hello"
i=i*2
endwhile
This will print "Hello" for i = {1,2,4,8,16,32} = 6 times
Number of time = floor(log2n) + 1
T(n) = θ(log n)
b) set n = 4
set i = 1
while i not equal to n
print "Hello"
i=i+2
endwhile
if n is even number, then while Loop will never stop(It will
print Infinite times)
if n is odd number, then it will print (n-1)/2 times
Number of time = (n-1)/2 times
T(n) = θ(n)
c) set n = 4
set i = 1
while i<= n
set j = 1
while j <= i
print "Hello"
j=j+1
endwhile
i=i+1
endwhile
when i=1, j={1} 1 times
when i=2 , j={1,2} 2 times
when i=3 , j={1,2,3} 3 times
when i=4 , j={1,2,3,4} 4 times
Total = (1 + 2 + 3 + 4) = 10 times
Number of time = n*(n+1)/2 times
T(n) = θ(n^2)