Question

1.) Answer the following questions based on the following pseudocode for the function “foo”:

Algorithm 1: foo

mystery()

foreach i ←1 to n do

mystery()

foreach j ←1 to i do

(A) Determine the exact number of times mystery() is called in terms of n.

(B) Assume the mystery function is in O(log(n) ∗ n ^2 ). Determine the complexity of “foo” in O-notation.

if i ≤ j then

mystery()

Answer 1

A)
Algorithm and number of times each line runs:
Algorithm 1: foo
mystery()       -> 1 time
foreach i ←1 to n do    -> n+1 times
mystery()               -> n times
foreach j ←1 to i do    -> n*(i+1) times

Number of times mystery() is called = 1 + n


----------------------------
B)
Time complexity 
= 1 + n+1 + n + n*(i+1)
Max value for i is n
>= 1 + n+1 + n + n*(n+1)
>= 2 + 2n + n*(n+1)
>= 2 + 2n + n^2 + n
>= 2 + 3n + n^2
>= n^2