Skip to content

Instantly share code, notes, and snippets.

@misterpoloy
Created April 19, 2020 11:05
Show Gist options
  • Save misterpoloy/d0599770436f6c778d62d7d28aabc7fe to your computer and use it in GitHub Desktop.
Save misterpoloy/d0599770436f6c778d62d7d28aabc7fe to your computer and use it in GitHub Desktop.
3 ways of exponesiation, iterative, recursive and dynamic
// https://www.youtube.com/watch?v=wAyrtLAeWvI&list=PL2_aWCzGMAwLz3g66WrxFGSXvSsvyfzCO&index=7
#include <iostream>
// Big(Log N) //if (n <= 1) return n; // Toggle^1/2 * Toggle^1/2
int expoIterativeBest(int x, int n) {
if (n == 0) return 1;
if (n % 2 == 0) {
int Y = expoIterativeBest(x, n - 1);
return Y * Y;
}
return x * expoIterativeBest(x, n - 1);
}
// Big(O)
int expoIterative(int x, int n) {
int result = x;
for (int i = 1; i < n; i++) {
result = result * x;
}
return result;
}
// Big O
// x^n = x * X^ n - 1 if n > 0 1 if n = 0
int expoRecurisve(int x, int n) {
if (n == 0) return 1;
return x * expoRecurisve(x, n - 1);
}
int main() {
int x = 3;
int n = 4;
std::cout << "Result iterative: " << expoRecurisve(x,n) << std::endl;
std::cout << "Result recursive naive: " << expoIterative(x, n) << std::endl;
std::cout << "Result recursive best: " << expoIterativeBest(x, n) << std::endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment