Tricky Looping

Computer Science Level 1

What is the Big-O Notation of the following code snippet?

product_prices = [10.25, 10.99, 11.50, 16.99]

n = len(product_prices)
while n > 0:
   print(product_prices[n-1])
   n = int(n / 2)

O(n/2)

O(log_{2}(n))

O(n)

O(n^{2})

1 solution

John Faucett
Oct 13, 2019

As the input size $n$ grows the number of steps taken by the while loop grows logarithmically.

We can see this by observing the number of times the while loop is executed for different $n$ values for the input list product_prices .

`n = len(product_prices)`	number of times while loop runs
4	3
8	4
16	5
32	6
64	7

It is even possible to see the logarithmic growth rate, without observation. A repeated multiplication is an exponential growth. A repeated division is the inverse operation and therefore is must be a logarithmic growth.

CodeCrafter 1 - 1 year, 7 months ago

Tricky Looping

1 solution

0 pending reports