Finding the BigO for the code given in Python
Given is a function below:
def count(n):
total= 0
i = 1
while i < n:
j = n
while j > 0:
total += j
j -= 1
i *= 2
return total
I am confused as to what the Big O for this question would be. I am thinking O(n*log(n))
. Is that right?
The answer to your question is O(n*log(n))
Take a number and try it:
def count(n=8):
total= 0
i = 1
while i < 8: #1,2,4 (log(8) -> log(n) iterations)
j = 8
while j > 0: #8,7,6,5,4,3,2,1 (8 -> n iterations)
total += j
j -= 1
i *= 2
return total
Hence, O(n*log(n))