algorithm - Timecomplexity analysis of function, Big O

Question

What time-complexity will the following code have in respect to the parameter size? Motivate.

// Process(A, N) is O(sqrt(N)). 

Function Complex(array[], size){
    if(size == 1) return 1;
    if(rand() / float(RAND_MAX) < 0.1){
        return Process(array, size*size)
             + Complex(array, size/2)
             + Process(array, size*size);
    }
}

I think it is O(N), because if Process(A, N) is O(sqrt(N)), then Process(A, N*N) should be O(N), and Complex(array, size/2) is O(log(n)) because it halves the size every time it runs. So on one run it takes O(N) + O(log(N)) + O(N) = O(N).

Please correct me and give me some hints on how I should think / proceed an assignment like this.

I appreciate all help and thanks in advance.

Answer 1

该算法的时间复杂度O(N)确实是，但原因不同。

函数的复杂度可以表示为T(n)：

T(n) = T(n/2)       +       2*n
        ^                   ^
      recursive          2 calls to 
      invokation        Process(arr,n*n),
                          each is O(n(

众所周知，这种递归是 O(n)：

T(n) = T(n/2) + 2*n = 
     = T(n/4) + 2*n/2 + 2*n = 
     = T(n/8) + 2*n/4 + 2*n/2 + 2*n
     = ....
     = 2*n / (2^logN) + ... + 2*n/2 + 2*n
     < 4n
     in O(n)

让我们正式证明它，我们将使用数学归纳法：

基数： T(1) < 4（检查）
假设：对于n，并且对于每个k<n声明T(k) < 4k 都成立。
对于n：

T(n) = T(n/2) + n*2 = (*) 
     < 2*n + 2*n 
     = 4n

结论：T(n)在O(n)

(*) 从归纳假设