CODEWITHSUNDEEP
algorithmtime-complexitybig-o
Rob Rorry
Rob Rorry

Reputation: 61

Find the Big O time complexity of the code

I am fairly familiar with simple time complexity regarding constant, linear, and quadratic time complexities. In simple code segments like: 

int i = 0;  
i + 1;

This is constant. So O(1). And in:

for (i = 0; i < N; i++)

This is linear since it iterates n+1 times, but for Big O time complexities we remove the constant, so just O(N). In nested for loops:

for (i = 0; i < N; i++) 
  for (j = 0; j < N; j++)

I get how we multiply n+1 by n and reach a time complexity of O(N^2). My issue is with slightly more complex versions of this. So, for example:

S = 0;
for (i = 0; i < N; i++) 
  for (j = 0; j < N*N; j++) 
    S++;

In such a case, would I be multiplying n+1 by the inner for loop time complexity, of which I presume is n^2? So the time complexity would be O(n^3)?

Another example is: 

 S = 0;
 for (i = 0; i < N; i++)
   for (j = 0; j < i*i; j++) 
     for (k = 0; k < j; k++) 
       S++;

In this case, I expanded it and wrote it out and realized that the inner, middle for loop seems to be running at an n*n time complexity, and the most inner for loop at the pace of j, which is also nxn. So in that case, would I be multiplying n+1 x n^2 x n^2, which would give me O(n^5)?

Also, I am still struggling to understand what kind of code has logarithmic time complexity. If someone could give me an algorithm or segment of code that performs at log(n) or n log(n) time complexity, and explain it, that would be much appreciated.

Upvotes: 4

Views: 320

Answers (1)

Ekesh Kumar
Ekesh Kumar

Reputation: 525

All of your answers are correct.

Logarithmic time complexity typically occurs when you're reducing the size of the problem by a constant factor on every iteration.

Here's an example:

for (int i = N; i >= 0; i /= 2) { .. do something ... }

In this for-loop, we're dividing the problem size by 2 on every iteration. We'll need approximately log_2(n) iterations prior to terminating. Hence, the algorithm runs in O(log(n)) time.

Another common example is the binary search algorithm, which searches a sorted interval for a value. In this procedure, we remove half of the values on each iteration (once again, we're reducing the size of the problem by a constant factor of 2). Hence, the runtime is O(log(n)).

Upvotes: 3

Related Questions