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)
