Question

Given the following Python function, find out an asymptotically tight bound of the algorithm in term of n (the input parameter). This function returns a list of n integers. Each element in the list contains the value f(i) = i + ⌊ i 2 ⁄ ⌋ + ⌊ i 4 ⁄ ⌋ + ⋯ 1. Write your answer as Python comments in the file csc220a2.py

Answer 1

Answer:

Explanation:

There are two loops in the given code snippet:

1. Both the loops are nested

2. The outer loop which is for loop is running n number of times linearly.

3. The inner loop which is while loop is jumping in the power of 2, which makes it run log n number of times.

So the overall complexity of the code will be= n * log n

Time complexity(or upper bound)= O(n log n).

Hit the thumbs up if you liked the answer. :)