-2

Hi guys I have an algorithm analysis exam tomorrow and I found this question online. I tried to solve it but I just need you to check if my solution is right

 public class t {
      public static void main(String[] args) {
      System.out.println(mystery(7, 6));
      }
      public static int mystery(int a, int b) {
      if (b == 0) return 0; 
      return mystery(a * 2, b / 2) + a;
      }
     }

My answer: This algorithm has complexity of O(logn) because each time b is rediced by half till we reach the terminating condition which is 1.

1
  • 1
    Sounds good to me. However, as Timothy pointed out, you need to be careful about the definition of N. For instance, if N is the number of bits of the input, your algorithm is actually O(N). (And an O(b) algorithm would be O(2^n))
    – hugomg
    Oct 30, 2015 at 19:02

1 Answer 1

4

O(log n) is wrong because there is no "n" defined.

While I know you mean that the complexity is O(log b), which is correct, you have to reference the correct variable. Otherwise it would be equally correct to assume that O(log n) means O(log a), which would be very incorrect.

Also, the stopping condition is b = 0.

7
  • I agree, you have two variables a and b for which you know you depend on in a O notation case, a and b are both assumed to be infinite since mystery(a, b) can produce any number a and b
    – AGE
    Oct 30, 2015 at 19:04
  • 'Any number'? No, both are integer values and so I doubt the method could produce .5, pi, or i for a few other values that are numeric as they exist in the Complex number system and thus beware of language.
    – JB King
    Oct 30, 2015 at 19:10
  • Being devils layer there is also another solution That is O(1) if you look for space complexity assuming tail recursion.
    – Luka Rahne
    Oct 30, 2015 at 19:13
  • @LukaRahne The function is not tail recursive, although it could be made to be tail recursive. That would not change the time complexity however. Oct 30, 2015 at 19:45
  • just to check one thing this fxn is called 3 times when b=6 right?
    – Mira
    Oct 31, 2015 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.