Python Big-O Examples

What are the Big-O for the following?

Some students in an Algorithms class I am teaching are having trouble with Big-O notation. Here are some practice problems:

Qs 1

for i in range(n):
       sum++
Answer
O(n)

Qs 2

for i in range(n)
     for j in range(n) 
            sum+=1 
Answer
O(n)

Qs 3

for i in range(n, - 1, -1):
	sum +=1
Answer
O(n^2)

Qs 4

i = 1
while i<n:
    i *= 2
Answer
O(2^n)

Qs 5

i = n
while (i < n)
     i ++    
Answer
O(1)

Qs 6

def fibonacci(n):
	if (n <= 1): return n
	else: return(fibonacci(n - 2) + fibonacci(n -1))
Answer
O(2^n)

Qs 7

i = 0 
while (i > n)
     i *= 2  
Answer
O(1)

Qs 8

for(int i=n; i>0; i/=2)
   for(int j=0; j<i; j++)
      count++;
Answer
O(n)

Qs 9

for(int i=1; i<n*n; i++)
    for(int j=1; j≤i; j++)
 	for(int k=1; k≤ 6; k++)
 	   sum ++;
Answer
O(n^4)
Avi Vajpeyi
Avi Vajpeyi
Astrophysics PhD Student

My research focuses on utilising Bayesian inference to the study gravitational waves from merging black holes.