CODEWITHSUNDEEP
javaalgorithmasymptotic-complexity
techPackets
techPackets

Reputation: 4506

Calculating the BigO for a code

I read an article online. The BigO for the below code as per my understanding should be O(n). As the loop runs n times. But the correct answer in the articles shows as O(1). With the explanation

The code declares exactly 4 variables: i, j, k and t. 4 = constant = O(1).

How?

As per my understanding, the loop runs n times hence O(n)

int fibonacci(int n)
{
   int i = 0, j = 1, k, t;
   for (k = 1; k <= n; ++k)
   {
     t = i + j;
     i = j;
     j = t;
   }
   return j;
}

Screenshot attached enter image description here

Upvotes: 1

Views: 1114

Answers (3)

Hashan Eranda
Hashan Eranda

Reputation: 31

If you pass 'n' a constant value it's Time Complexity O(1)

// Here c is a constant   


for (int i = 1; i <= c; i++) {  
        // some O(1) expressions
   }

A loop or recursion that runs a constant number of times is also considered as O(1).

If you pass 'n' a variable it's Time Complexity O(n).

 // Here c is a positive integer constant   


for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount.

Source: http://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/

Upvotes: -1

Josh Evans
Josh Evans

Reputation: 655

You've mistaken memory complexity for time complexity. The time complexity of the algorithm is O(n). However, the memory, sometimes called space, complexity of the algorithm is O(1), as 4 variables are allocated.

Upvotes: 11

Soumyajyoti Bhattacharya
Soumyajyoti Bhattacharya

Reputation: 265

Formally, big-O notation describes the degree of complexity.

To calculate big-O notation:

identify formula for algorithm complexity. Let's say, for example, two loops with another one nested inside, then another three loops not nested: 2N² + 3N remove everything except the highest term: 2N² remove all constants: N² In other words two loops with another one nested inside, then another three loops not nested is O(N²)

This of course assumes that what you have in your loops are simple instructions. If you have for example sort() inside the loop, you'll have to multiply complexity of the loop by the complexity of the sort() implementation your underlying language/library is using

By the mathematical logic of it, the Big O notation for your program is O(N), and not O(1). In which case, either the article is wrong, or your understanding of what it is saying is incorrect and incomplete, with only the partial text being put over here.

Upvotes: 1

Related Questions