Question

For each C++ function below, give the tightest can asymptotic upper bound that you can determine. (a) void mochalatte(int n) { for (int i = 0: i < n: i++) { count < < "iteration;" < < i < < end1: } } (b) void nanaimobar (int n) { for (int i = 1: i < 2*n: i = 2*i) { count < < "iteration;" < < i < < end1: } } void appletart (int n) { for (int i = 0: i < 3*n: i = I + 3) { for (int j = 0: j*j < 2*n: j++) { count < < "iteration;" < < j < < end1: } }

Answer 1

Answer is as follows:

The Asymptotic Upper bound is represend in bigO notation.

A)

The function has a for loop that work for i to n times mean it runs n times.

for other statements it is O(1)

So O(n) + O(1)

the largest part is O(n)

So the Big O notation for this is function is O(n).

B)

The function has a for loop that work for i to 2*n times mean it runs 2n times.

for other statements like cout function it is O(1)

So, O(1) + O(2n)

the largest part is O(2n)

According to rules O(n) = O(2n)

Proof:

if O(n) is subset of O(2n) => Let g be the function in O(n) . There are N and c>0 such that g(n) < c*n for all n>N. Thus g is in O(2n).

if O(2n) is subset of O(n) => Let g be the function in O(n) . There are N and c>0 such that g(n) < c*2n for all n>N. So g(n) < 2c * n for all n > N. Thus g is in O(n).

So the Big O notation for this is function is O(2n) as well as O(n).

C)

The function cotains the two for loops i.e. it works for n x n times or 3n x 2n times as state above n=2n=3n are equal.

So we the Big O notation for nested For loops are n² .

For other statements it isO(1).

So the BigO notation for this is O(n² )

if there is any query please ask in comments...........