rajkumar-p

The two recurrence equations that we have seen earlier are,
T(n) = 4T(n/2) + f(n) and T(n) = 3T(n/2) + f(n).
In the equation T(n) = 4T(n/2) + f(n), a = 4 and b = 2, hence f(n) = O(n^2), hence the runtime is T(n) <= O(n ^ 2)
In the equation T(n) = 3T(n/2) + f(n), a = 3 and b = 2, hence f(n) = O(n^1.5), hence the runtime is T(n) <= O(n ^ 1.5)

rajkumar-p

Let, a = first n/2 digits of X  
b = last n/2 digits of X
c = first n/2 digits of Y
d = last n/2 digits of Y

X = (10 ^ n/2)a + b
Y = (10 ^ n/2)c + d

The guass trick is as follows, 
1) Compute AC

rajkumar-p

Let, a = first n/2 digits of X  
b = last n/2 digits of X
c = first n/2 digits of Y
d = last n/2 digits of Y

X = (10 ^ n/2)a + b
Y = (10 ^ n/2)c + d

And, X * Y = ((10 ^ n/2)a + b)*((10 ^ n/2)c + d)
X * Y => 10^2 ac + 10^n/2 (ad + bc) + bd

rajkumar-p

for(int i = X.length() - 1; i >= 0; ++i) {  
    for(int j = Y.length() - 1; j >= 0; ++j) {  
        // Multiplication logic goes here  
    }
}

rajkumar-p

int karatsuba(int X, int Y) {
  int digits = getOrderOfNumber(min(X, Y));

	// base condition
	if (digits == 1) {
		return X * Y;
	}

	int bm = pow(static_cast<double>(10), digits/2);

rajkumar-p

int fibonacci(int n) {
	int fibonacci_of_n = 0;
	// Base condition
	if (n == 1 || n == 0) {
		return n;
	}
	else {
		// n - 1
		int n_minus_1 = 1;
		// n - 2

rajkumar-p

int fibonacci(int n) {
	// Base condition
	if (n == 1 || n == 0) {
		return n;
	}
	else {
		// else return F(n - 2) + F(n - 1)
		return fibonacci(n - 2) + fibonacci(n - 1);
	}
}

rajkumar-p

#include <iostream>
using namespace std;

int main() {

	int i_arr[2][2][2] = {
			{
					{1, 2},
					{3, 4}
			},

rajkumar-p

#include <iostream>
using namespace std;

int main() {

	int i_2d_arr [3][5] = { {4, 2, 7, 8, 1},
			{12, 19, 15, 16, 11},
			{23, 28, 22, 29, 28}
	};

rajkumar-p

#include <iostream>
using namespace std;

int main() {

	int i_2d_arr [3][5] = { {4, 2, 7, 8, 1},
			{12, 19, 15, 16, 11},
			{23, 28, 22, 29, 28}
	};