# CodeStepByStep

## bigoh_examples

Language/Type: Python algorithm analysis big-oh

Give a tight bound of the nearest runtime complexity class for each of the following code fragments in Big-Oh notation, in terms of the variable N. In other words, write the code's growth rate as N grows. Write a simple expression that gives only a power of N using a caret `^` character for exponentiation, such as `O(N^2)` to represent O(N2) or `O(log N)` to represent O(log2 N). Do not write an exact calculation of the runtime such as O(2N3 + 4N + 14).

```a)
sum = 0
j = 1
while j <= n:
sum += 1
j *= 2
print(sum)
```

```b)
sum = 0
for j in range(1, n):
sum += 1
if j % 2 == 0:
sum += 1
print(sum)
```

```c)
sum = 0
for i in range(1, n * 2 + 1):
for j in range(1, n + 1):
sum += 1

for j in range(1, 100):
sum += 1
sum += 1
```

```d)
sum = 0
for i in range(1, n + 1):
for j in range(1, i + 1, 2):
sum += 4
for k in range(-50, -2):
sum += 1
```
 a) O(1) O(log N) O(N) O(N log N) O(N^2) O(N^2 log N) O(N^3) O(2^N) O(N^N) b) O(1) O(log N) O(N) O(N log N) O(N^2) O(N^2 log N) O(N^3) O(2^N) O(N^N) c) O(1) O(log N) O(N) O(N log N) O(N^2) O(N^2 log N) O(N^3) O(2^N) O(N^N) d) O(1) O(log N) O(N) O(N log N) O(N^2) O(N^2 log N) O(N^3) O(2^N) O(N^N)