CODEWITHSUNDEEP
c++algorithmtime-complexitycomplexity-theorycode-complexity
user15329767
user15329767

Reputation:

How can I calculate the complexity of a program like this

So I have been studying the complexity of algorithms, but this one I can't uderstand. If I use a global variable to check how many times the function is called it will calculate the number 11 then saying that the complexity is O(2*N), but when looking at the problem I thought the complexity would be O(N).

#include <cstdlib>
#include <iostream>
  
using namespace std;
  
class node { 
    public:
    int data; 
    node* left; 
    node* right; 
      
    node(int data){
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
}; 

int funcUtil(node* node, int min, int max) { 
    cout << "a";
    if (node==NULL)
        return 1; 
    
    if (node->data < min || node->data > max)
        return 0; 
    
    return funcUtil(node->left, min, node->data-1) && funcUtil(node->right, node->data+1, max);
} 

int func(node* node) { 
    return(funcUtil(node, INT_MIN, INT_MAX)); 
} 
  
int main() { 
    node *root = new node(4); 
    root->left = new node(2);  
    root->right = new node(5); 
    root->left->left = new node(1); 
    root->left->right = new node(3); 
      
    if(func(root)) 
        cout<<"YES"; 
    else
        cout<<"NO"; 
          
    return 0; 
}

Upvotes: 0

Views: 675

Answers (3)

NANDINI KAUSHAL
NANDINI KAUSHAL

Reputation: 1

Fundamentally if you look at the meaning of big-O it means that the growth rate of a function f is slower than the function g(n) so we write f(n) = O(g(n)).

Now think of it as n and 2n will always be having the same growth rate as they change with change in n so which brings us to the conclusion that O(n) is that same as O(2n), and now we will be using O(n) as it is the standard form to depict linear growth rate.

Upvotes: 0

klutt
klutt

Reputation: 31389

Big O notation works like this:

O(c * f(x)) = O(f(x)), c!=0

In other words, you can always multiply the function inside the parenthesis by an arbitrary non-zero real constant.

So O(2N) = O(N)

Another property of big O notation is that you can omit lower order terms:

O(x^2 + x) = O(x^2)

O(a^x + p(x)) = O(a^x) where a>1 and p(x) is a polynomial of x

Further reading: https://en.wikipedia.org/wiki/Big_O_notation

Upvotes: 1

Abhinav Batta
Abhinav Batta

Reputation: 11

The complexity of O(2*N) is same as that of O(N), the constants are omitted.

Upvotes: 0

Related Questions