CODEWITHSUNDEEP
calgorithmtime-complexitybig-o
user6918211
user6918211

Reputation: 1

Need explanation of time complexity solution of algorithm

My intro to software engineering class has just hit time complexity and learning how to analyze certain algorithms. I'm having difficulty seeing how they got to their solution and was hoping someone could explain it, hopefully with some logical proof?

void foo(int N) {
    int k = 1;
    while (k < N * N) {
        k = k * 2;
    }
}

Their solution is that Big-O of this function is O(logN) [I understand that log here is base 2]

I tried to solve this by thinking how many times it would iterate by assigning random values to N and I couldn't find a pattern, any help?

Upvotes: 0

Views: 57

Answers (2)

Gene
Gene

Reputation: 46960

Use your high school algebra. After p iterations the value of k is 2^p. (It's easy to check this.) The loop will stop executing when k >= N^2. Substituting, the loop stops when

2^p >= N^2

Now solve:

log_2(2^p) >= log(N^2)
p >= 2 log(N)

So the loop will stop at very close to 2 log(N) iterations. This is O(log(N)).

You might take your teacher to task by pointing out that multiplication is constant time only if there's a fixed limit on the size of operands. With no such limit, the problem depends on the asymptotic behavior of multiplication as well.

Incidentally, O(log N) is the same for all bases of the logarithm. The base changes the value of the log only by a constant factor, and big-O ignores constant factors.

Upvotes: 2

Charles
Charles

Reputation: 1396

The fact that k is being increased by a factor of 2 each time is what makes the algorithm logN. Actually, it's log(N^2), but using the properties of logarithms we can simplify it to 2log(N) and then drop the 2 by taking the limit as N approaches infinity to get log(N).

Thus, the time complexity is O(logN).

EDIT: Additionally, it can be seen that k starts at 1 and the program ends when k is greater than or equal to N * N. If we take the log(N^2), we will know how many iterations through which the program will run. In doing so, we will also be able to determine the ending value of k by taking the ceiling of log(N^2).

EDIT: An example would be N = 10: The square of N is 100. Thus, k will increase until the power of two above or equal to 100, which is 128.

Upvotes: 2

Related Questions