Skip to content

Instantly share code, notes, and snippets.

@codistwa
Last active February 23, 2022 15:27
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save codistwa/d6c1441cde0e2a5aadb7abb00b16c45b to your computer and use it in GitHub Desktop.
Save codistwa/d6c1441cde0e2a5aadb7abb00b16c45b to your computer and use it in GitHub Desktop.
// ============================================================
// 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
# ============================================================
# 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