Power function

Date and time note was created	$= dv.current().file.ctime
Date and time note was modified	$= dv.current().file.mtime

Question Link :

Question Breakdown

This question can be solved in the following ways

• By Recursion
• By Iterative approach in programming

Approaches

Brute Force / Recursive approach

Algorithm

• We take decision if base case is to be resolved or to break down the problem
• We break down the problem using $x^n=x\ast x^{n-1}$
• Base case for the problem at which the problem stops recursion $x^0=1$

Code

 
int power(int x,int n){
	// [[Base Case In Recursion]]
	//( As we already know the answer to the problem x^0=1)
	if(n==0)
		return 1;
	int res=power(x,n-1);
	// [[Recursive relation]]
	//Breaking down the unsolvable problem into [[smaller problems]]
	return x * res;
}
int main(){
  cout<<power(2,6);
  return 0;
}

Time Complexity

$O(n)\ast O(1)=O(n)$

Space Complexity

$O(n)$

From Time Complexity and Space Complexity in recursion we can say O(n) is the number of the calls made and O(1) is the time for each call. Also the Space complexity in this case is O(n) as n calls gets stored in the Call Stack.

Optimised / Iterative Approach

Algorithm

Code

Time Complexity

$O()$

Space Complexity

$O()$

Related

• Recursion

References

Foot notes

Call stack developed during the execution of the above code can be illustrated as follows:

References::

Tags::

Back-links:: Time Complexity and Space Complexity in recursion Call Stack

Foot-notes::