What algorithm can I use to compute 2022^n (given n \in N)? How can I prove the correctness (maybe induction?) and what's the upper bound used?

Question

I have to use n-1 multiplications but I am confused about proving the correctness of the algorithm and finding the upper bound. How do I do/show that??

I know 2022 = 20*(100+1)+2
2022 = 2000+20+2 ......
2022 = 2000+2+2+..+2 etc.

Answer 1

I'm not sure why you are breaking 2022 into additions. m^n means to multiply m by itself n times, e.g.:

2022^n = 2022 * 2022 * ... * 2022.

Note 2022 appears n times (this is the definition of raising a number to a power), and there are n-1 multiplication operations.

For example, 2022^2 = 2022 * 2022. There is one multiplication operation.

You can accomplish this in code like this (C# here, but the concept applies to every language):

long m = 2022;
long n = 3;

long counter = 1;

for (int i = 0; i < n; i++)
  counter = counter * m;
  
Console.WriteLine(counter);

Note that raising 2022 to even a modestly large value for n will overflow 64-bit integer types. You can still get a good approximation for larger n using floating point types.

As mentioned in the comments, a more efficient but less obvious approach is exponentation by squaring.