Big O confusion about upper bound of an algorithm

Question

I dont know why I am getting confused about this as this is relatively simple but I am going to ask anyway...

Consider the following algorithm: Given a value k, compute a^k, and binary search for a^k in an array of size N. Consider the fact that multiplication takes O(log₂(a)^k) time.

What would the total runtime for this algorithm be? Here are my thoughts:

In the worst case, binary search will make log₂(N) comparisons, and for each comparison, it takes O(log₂(a)^k) to calculate a^k. So the total would be O(log₂(a)^k(log₂(N)))? Am I going about this the correct way?

Answer 1

Presumably you compute $a^k$ once, then search for it in the array. You should not multiply the number of operations for each part, you should add them. Using binary search assumes that the array is sorted, but we will accept that. You are right that you will do $\log_2 N$ comparisons. To compute $a^k$ you can express $k$ in binary, square $a$ enough times, then multiply the values that correspond to the one bits in $k$. You should be able to express this in terms of the number of bits in $a$, which is $\log_2 a$ and a function of $k$.