How many times is the function 'YellowJackets' called in the functions below? Give an exact bound and a tight asymptotic bound in Big-O notation. Show your work (summations and closed forms), but no formal proof is necessary. a) function A(n) for i = 0, i <= n, i = i + 1 do for j = i, j <= n^2, j = j + 1 do YellowJackets() end for end for end function b) function B(n) for i = 0, i <= n, i = i + 1 do for j = 0, j <= n, j = j + 2 do YellowJackets() end for end for for k = 0, k < n, k = k + 1 do YellowJackets() end for end function c) function C(n) for i = 1, i <= n, i = i + 1 do for j = 1, j <= n, j = j ∗ 2 do YellowJackets() end for end for end function d) function D(n) i = 1 while i < n^4 do i = i + 2 for j = i, j <= n^3, j = j + 1 do YellowJackets() end for YellowJackets() end while end function
Question:
How many times is the function 'YellowJackets' called in the functions below? Give an exact bound and a tight asymptotic bound in Big-O notation. Show your work (summations and closed forms), but no formal proof is necessary.
a) function A(n)
for i = 0, i <= n, i = i + 1 do
for j = i, j <= n^2, j = j + 1 do
YellowJackets()
end for
end for
end function
b) function B(n)
for i = 0, i <= n, i = i + 1 do
for j = 0, j <= n, j = j + 2 do
YellowJackets()
end for
end for
for k = 0, k < n, k = k + 1 do
YellowJackets()
end for
end function
c) function C(n)
for i = 1, i <= n, i = i + 1 do
for j = 1, j <= n, j = j ∗ 2 do
YellowJackets()
end for
end for
end function
d) function D(n)
i = 1
while i < n^4 do
i = i + 2
for j = i, j <= n^3, j = j + 1 do
YellowJackets()
end for
YellowJackets()
end while
end function
Step by step
Solved in 4 steps
