Time Complexity of series of algorithms

Question

I have some doubts about the time complexities of these algorithms:

These are all the possible options for these algorithms

Algorithm 1

int i=0, j=0, sum = 0;  
  while i*i < n {
    while j*j < n {
      sum = sum + i * j;
      j = j+2;
    }
   i = i+5;
  }

//I don't really know what this one might be, but my poor logic suggests O(sqrt(n))

Algorithm 2

sum = 0;
for (i=0; i<=n; i++){  
  j = n;
  while j>i {
    sum = sum + j - i; 
    j = j – 1;
  }
}

//While I know this algorithm has some nested loops, I don't know if the actual answer is O(n^2)

Algorithm 3

for (int i=0; i<=n; i++)
  for (int j=0; j<=n; j++){
    k = 0;
    while k<n {
        c = c+ 1;
        k = K + 100;
    }
}

//I believe this one has a time complexity of O(n^3) since it has 3 nested loops

Algorithm 4

Algorithm int f(int n) {
if n==0 or n == 1
return n
else    
    return f(n-2)+f(n-1)

//I know for a fact this algorithm is O(2^n) since it is the poor implementation of fibonacci

I think I have an idea of what the answers might be but I would like to get a second opinion on them. Thanks in advance.

Why don't you post what you believe the answers to be along with an explanation of why you think that? Otherwise it kind of feels like you are just trying to get people to do your homework for you. — Tony Tuttle, Apr 12 '18 at 17:24

score 1 · Accepted Answer · answered Apr 12 '18 at 18:00

Okay so this is what I think, Answers in bold

Algorithm 1

I think this is the most interesting algorithm. Let's build it up from a simple case

Let's temporarily assume it was just 2 nested loops that just checked for i,j being <n and not the the squares of those values. Now the fact that i and j get incremented by 5 and 2 respectively is inconsequential. And the complexity would have just been O(n²).

Now let's factor in the fact that the check is in fact i*i < n and j * j < n. This means that effective value ofyour iterators is their square and not just their absolute value. If it had been just one loop the complexity would have been O(sqrt(n)). But since we have 2 nested loops the complexity become O(sqrt(n) * sqrt(n)) which becomes O(n)

Algorithm 2

Your reasoning is right. It is O(n²)

Algorithm 3

Your reasoning is right. It is O(n³)

Algorithm 4

I don't think this is a fibonacci implementation but your time complexity guess is correct. Why I don't think this is a fibonacci is because this algorithm takes in a large number and works in reverse. You could send in something like 10 which isn't even a fibonacci number.

A nice way to think of this is as a binary tree. Every node, in your case every call to the fn that is not 1 or 0 spawns 2 children. Each call minimally removes 1 from the initial value sent in, say n. Therefore there would be n levels. The maximum number of nodes in a binary tree of depth n is 2ⁿ - 1. Therefore O(2ⁿ) is right

Thanks a lot. Your explanations really helped me visualize it. — Kelvin G.M., Apr 12 '18 at 19:14
@KelvinG.M. a quick thing to note, `j` isn't being reset in the first algorithm. I assumed that omission was a typo. If it wasn't then the time is just ***O*(*sqrt*(n))** — Srini, Apr 12 '18 at 19:21
Also, the tightest bound of algorithm 4 is not given by `2^n` but `1.618^n` — meowgoesthedog, Apr 12 '18 at 19:22
@meowgoesthedog could you please elaborate :)? I'm interested in knowing how to deduce that — Srini, Apr 12 '18 at 19:25
See the second answer on [this page](https://stackoverflow.com/questions/360748/computational-complexity-of-fibonacci-sequence). — meowgoesthedog, Apr 12 '18 at 19:45

Time Complexity of series of algorithms

1 Answers1

Algorithm 1

Algorithm 2

Algorithm 3

Algorithm 4