Time complexity for a function with two arguments

user_17182982 0
Viewed 117

I'm currently studying how to figure out the time complexity of functions but I'm struggling a bit with the subject so far, and I came across a scenario that I really don't understand how to solve.

For the following function:

fun fun1(n: Int, m: Int): Int{
   if(n/m == 0)
      return 0
   else
      return 1 + fun1(n/m, m)
}

I have to figure out it's time complexity in two different situations:

a) When m has a set value of 2 (m = 2 for any n)

b) n and m don't have set values

I believe that in either case the complexity would be O(n) for either of them but I'm having a hard time putting that conclusion into an expression, specially for the case where n and m can have any value.

Thank you in advance for any help!

big-o time-complexity algorithm
2 Answers

The easier way to visualize is to fit in some numbers.

Let say, n = 32, m = 2, in every recursive call you will reduce n by 2 time, so

          n  
call #1: 32  
call #2: 16  
call #3:  8  
call #4:  4  
call #5:  2  
call #6:  1

The complexity of the program is basically the number of call * the complexity of the non-recursive part

user_99653840

The complexity is Theta(log_m(n)), or equivalently Theta(log n / log m) using a log rule.

The function finds the lowest integer a such that m^a >= n, and it does this is a steps. That's ceil(log_m(n)) = ceil(log(n) / log(m)) steps.

If m is fixed (and m>1), you can write it as Theta(log n).

If you want a 1-variable form, you can use O(log n) (as long as m>1), but the tight bound needs both variables.

user_14007930
Related