Last active
February 23, 2022 15:27
-
-
Save codistwa/d6c1441cde0e2a5aadb7abb00b16c45b to your computer and use it in GitHub Desktop.
Course source code: https://codistwa.com/guides/big-o-notation-and-complexity-time. More courses on https://codistwa.com
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// ============================================================ | |
// O(1) : constant complexity | |
// ============================================================ | |
function constantO(num) { | |
return num; | |
} | |
console.log(constantO(10)); // 10 | |
// ============================================================ | |
// O(log(n)) : logarithmic complexity | |
// ============================================================ | |
function logarithmic(num) { | |
for (i = 1; i <= num; i *= 2) { | |
console.log(i); | |
} | |
} | |
logarithmic(256); // 1 2 4 8 16 32 64 128 256 | |
// ============================================================ | |
// O(n) : linear complexity | |
// ============================================================ | |
function linear(num) { | |
for (let i = 0; i < num; i++) { | |
console.log(i); | |
} | |
} | |
console.log(linear(10)); | |
// ============================================================ | |
// O(nlog(n)) : linearithmic complexity | |
// ============================================================ | |
function linearithmic(num) { | |
for (let i = 1; i <= num; i++) { | |
for (let j = 1; j < num; j *= 2) { | |
console.log(i, j) | |
} | |
} | |
} | |
console.log(linearithmic(4)); | |
// ============================================================ | |
// (On^2) quadratic complexity / (On^p) polynomial complexity | |
// ============================================================ | |
function quadratic(num) { | |
for (let i = 1; i <= num; i++) { | |
for (let j = 1; j <= num; j++) { | |
console.log(i, j) | |
} | |
} | |
} | |
console.log(quadratic(4)); // 16 executions | |
function cubic(num) { | |
for (let i = 1; i <= num; i++) { | |
for (let j = 1; j <= num; j++) { | |
for (let k = 1; k <= num; k++) { | |
console.log(i, j, k) | |
} | |
} | |
} | |
} | |
console.log(cubic(4)); // 64 executions | |
function quadric(num) { | |
for (let i = 1; i <= num; i++) { | |
for (let j = 1; j <= num; j++) { | |
for (let k = 1; k <= num; k++) { | |
for (let l = 1; l <= num; l++) { | |
console.log(i, j, k, l) | |
} | |
} | |
} | |
} | |
} | |
console.log(quadric(4)); // 256 executions | |
// ============================================================ | |
// O(2^n): exponential complexity | |
// ============================================================ | |
function power (base, exponent) { | |
if (exponent === 0) { | |
return 1 | |
} | |
return base * power(base, exponent - 1) | |
} | |
console.log(power(2, 6)); // 64 | |
console.log(power(3, 6)); // 729 | |
// ============================================================ | |
// O(n!) : factorial complexity | |
// ============================================================ | |
function factorial(num) { | |
if (num === 1) { | |
return 1; | |
} | |
return num * factorial(num - 1); | |
} | |
function exponential(num) { | |
for (let i = 1; i <= factorial(num); i++) { | |
console.log(i) | |
} | |
} | |
console.log(exponential(6)); // 720 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# ============================================================ | |
# O(1) : constant complexity | |
# ============================================================ | |
def constant_o(num): | |
return num | |
print(constant_o(10)) # 10 | |
# ============== # | |
plt.axhline(0, label='$O(1)$') | |
plt.axis([-1, 6, -1, 6]) | |
plt.xlabel('x') | |
plt.ylabel('y') | |
plt.legend() | |
plt.grid() | |
plt.title('Constant', fontsize=12) | |
plt.savefig('constant.png', bbox_inches='tight') | |
plt.show() | |
# ============================================================ | |
# O(log(n)) : logarithmic complexity | |
# ============================================================ | |
x = np.linspace(-6,6, 100) | |
log = np.log2(x) | |
plt.plot(x, log, label='$O(log(x))$') | |
plt.xlabel('x') | |
plt.ylabel('y') | |
plt.legend() | |
plt.grid() | |
plt.title('logarithmic',fontsize=12) | |
plt.savefig('logarithmic.png', bbox_inches='tight') | |
plt.show() | |
# ============================================================ | |
# O(n) : linear complexity | |
# ============================================================ | |
def linear(num): | |
for x in range(num): | |
print(x) | |
print(linear(10)) | |
# ============= # | |
x = np.linspace(-6,6, 100) | |
l = x | |
plt.plot(x, l, label='$O(x)$') | |
plt.xlabel('x') | |
plt.ylabel('y') | |
plt.legend() | |
plt.grid() | |
plt.title('linear',fontsize=12) | |
plt.savefig('linear.png', bbox_inches='tight') | |
plt.show() | |
# ============================================================ | |
# O(nlog(n)) : linearithmic complexity | |
# ============================================================ | |
x = np.linspace(-6,6, 100) | |
l_g = x * np.log2(x) | |
plt.plot(x, l_g, label='$O(xlog(x))$') | |
plt.xlabel('x') | |
plt.ylabel('y') | |
plt.legend() | |
plt.grid() | |
plt.title('linearithmic',fontsize=12) | |
plt.savefig('linearithmic.png', bbox_inches='tight') | |
plt.show() | |
# ============================================================ | |
# (On^2) quadratic complexity / (On^p) polynomial complexity | |
# ============================================================ | |
def quadratic(num): | |
for i in range(num +1): | |
for j in range(num+1): | |
print(i, j) | |
print(quadratic(4)) # 16 executions | |
def cubic(num): | |
for i in range(num): | |
for j in range(num): | |
for k in range(num): | |
print(i, j, k) | |
print(cubic(4)) # 64 executions | |
def quadric(num): | |
for i in range(num): | |
for j in range(num): | |
for k in range(num): | |
for l in range(num): | |
print(i, j, k, l) | |
print(quadric(4)) # 256 executions | |
# ============= # | |
x = np.linspace(-6,6, 100) | |
q = x ** 2 | |
plt.plot(x, q, label='$O(n^2)$') | |
plt.xlabel('x') | |
plt.ylabel('y') | |
plt.axis([0,6,0,6]) | |
plt.legend() | |
plt.grid() | |
plt.title('quadratic',fontsize=12) | |
plt.savefig('quadratic.png', bbox_inches='tight') | |
plt.show() | |
# ============================================================ | |
# O(2^n): exponential complexity | |
# ============================================================ | |
x = np.linspace(-6,6, 100) | |
e = 2 ** x | |
plt.plot(x, e, label='$O(2^n)$') | |
plt.xlabel('x') | |
plt.ylabel('y') | |
plt.legend() | |
plt.grid() | |
plt.title('exponential',fontsize=12) | |
plt.savefig('exponential.png', bbox_inches='tight') | |
plt.show() | |
# ============================================================ | |
# O(n!) : factorial complexity | |
# ============================================================ | |
def factorial(num): | |
if num == 1: | |
return 1 | |
return num * factorial(num - 1) | |
def exponential(num): | |
for x in range(factorial(num)+1): | |
print(x) | |
print(exponential(6)) # 720 | |
# ============== # | |
x = np.linspace(-6,6, 100) | |
g = factorial(x) | |
plt.plot(x, g, label='$O(n!)$') | |
plt.xlabel('x') | |
plt.ylabel('y') | |
plt.legend() | |
plt.grid() | |
plt.title('factorial',fontsize=12) | |
plt.savefig('factorial.png', bbox_inches='tight') | |
plt.show() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment