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; 
} 

CodePudding user response：

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

CodePudding user response：

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