Cacher is the code snippet organizer for pro developers

1)

 int a = 0; 
    for (i = 0; i < N; i++) { 
        for (j = N; j > i; j--) { 
            a = a + i + j; 
        } 
    }


Ans : 
????

Count the number of times the loop runs.

When i = 0, it runs for N times.

When i = 1, it runs for N - 1 times …

When i = k, it runs for N - k times


So, total number of runs = N + (N - 1) + (N - 2) + … 1 + 0 = ???Total number of runs = N + (N - 1)
 + (N - 2) + … 1 + 0

= N * (N + 1) / 2

= 1/2 * N^2 + 1/2 * N

O(N^2) times.



Ans : 
O(N*N)

https://slimwiki.com/own-company/time-complexity1/7

6/22/2017own company Wiki — Time Complexity (leetCode)


2)

int a = 0, i = N; 
        while (i > 0) { 
            a += i; 
            i /= 2; 
        }


Ans:

Notice that in every iteration, i goes to i / 2

So, a er x iterations, i will be N / 2^x


We have to find first x such that N / 2^x < 1 OR 2^x > N

We have to find the smallest x such that N / 2^x < 1 OR 2^x > N


x = log(N)


Ans: O(log N)


3)


 int count = 0; 
        for (int i = N; i > 0; i /= 2) { 
            for (int j = 0; j < i; j++) { 
                count += 1; 
            } 
        }


Ans: 


In the first iteration, the j loop runs N times.

In the second iteration, the j loop runs N / 2 times.

In the ith iteration, the j loop runs N / 2^i times.

So, the total number of runs of loop = N + N / 2 + N / 4 + … 1

= N * ( 1 + 1/2 + 1/4 + 1/8 + … ) < 2 * N

Ans: O(N)

4)


int i, j, k = 0; 
    for (i  = n/2; i <= n; i++) { 
        for (j = 2; j <= n; j = j * 2) { 
            k = k + n/2; 
        } 
    }



Ans: Note the inner loop. It does not depend on value of i.


Can you  nd out how many iterations does j run for value of n ? Maybe try a few values of n, and check how
many times the loop will run. Do you see a pattern ?

Can you say something about how fast j is growing ?
k
What will j’s value be a er k iterations ? 2  ?
k
If 2  = n, then what is k ?



Now, lets just assume n = 8 for now.  
We will try to see, the values of j corresponding to each i.


i = 4, j = 2, 4, 8 
i = 5, j = 2, 4, 8 
i = 6, j = 2, 4, 8 
i = 7, j = 2, 4, 8 
i = 8, j = 2, 4, 8 

If you notice, j keeps doubling till it is less than or equal to n. Number of times, you can double a number till it is less than
n would be log(n).

Lets take more examples here to convince ourselves.


 n = 16, j = 2, 4, 8, 16 
 n = 32, j = 2, 4, 8, 16, 32 

So, j would run for O(log n) steps.  
i runs for n/2 steps.

So, total steps ` = O (n/ 2 * log (n)) = O(n logn) `

Ans: O (n/ 2 * log (n)) = O(n logn) `

5)********

In the following C++ function, let n >= m.


    int gcd(int n, int m) { 
            if (n%m ==0) return m; 
            if (n < m) swap(n, m); 
            while (m > 0) { 
                n = n%m; 
                swap(n, m); 
            } 
            return n; 
    } 

What is the time complexity of the above function assuming n > m?



Ans: Let us say n = fibonacci(N) and m = fibonacci(N - 1)

fibonacci(N) = fibonacci(N-1) + fibonacci(N-2)

https://slimwiki.com/own-company/time-complexity3/7

6/22/2017own company Wiki — Time Complexity (leetCode)
OR n = m + k where k < m.

Therefore the step


n = n % m will make n = k 

swap(n, m) will result in 

n = fibonacci(N-1) 

m = k = fibonacci(N-2) 

So, it will take N steps before m becomes 0.

This means, in the worst case, this algorithm can take N step if n is Nth fibonacci number.

Think of whats the relation between N and n.

Ans: Θ(logn)

5)
Which of the following is not bounded by O(n^2)?

Options:

A) (15^10) * n + 12099
B)  n^1.98
C) n^3 / (sqrt(n))
D) (2^20) * n

Ans: Look at the order of growth. Which function grows faster than O(n^2) ?
The order of growth of option (C) is n^2.5 which is higher than n^2.

Lets look at it with a di erent approach :


f(n) = O(n^2) if 
f(n) <= C * n^2 for n > n0. 

Lets look at every option one by one.

Option 1 :

   (15^10) * n + 12099 
    Lets say C = 16^10 
        15^10 * n + 12099 < 16^10 * n^2 for n > 1. 
    So, it is O(n^2). 

Option 2 : n^1.98

    C = 1. 
        n^1.98 < n^2 for n > 1. 
    So, its O(n^2) 

Option 3 : n^3 / (sqrt(n)) or n^2.5

    There is no possible combination of C and n0 possible 

Option 4 : 2^20 * n


    C = 2^20, n0 = 1 
        2^20 * n <= 2^20 * n^2 for n > 1

Ans: n^3 / (sqrt(n))

6)

 A) for(i = 0; i < n; i++) 

  B) for(i = 0; i < n; i += 2) 

  C) for(i = 1; i < n; i *= 2) 

  D) for(i = n; i > -1; i /= 2) 

Find complexity of all.

Ans: 
The time complexity of the  rst for loop is O(n).
The time complexity of the second for loop is O(n/2), equivalent to O(n) in asymptotic analysis.

The time complexity of the third for loop is O(logn).

The fourth for loop doesn’t terminate.

7) 
What is the worst case time complexity of the following code :


/*  
 * V is sorted  
 * V.size() = N 
 * The function is initially called as searchNumOccurrence(V, k, 0, N-1) 
 */ 
int searchNumOccurrence(vector<int> &V, int k, int start, int end) { 
    if (start > end) return 0; 
    int mid = (start + end) / 2; 
    if (V[mid] < k) return searchNumOccurrence(V, k, mid + 1, end); 
    if (V[mid] > k) return searchNumOccurrence(V, k, start, mid - 1); 
    return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end); 
}


Ans: 


It might seem at the first look that the program is O(log N). 

However, the last case


return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end); 

is the bottleneck step.  
Assuming all the values in the array are the same, we get the following relation :



T(N) = 2 * T(N/2) + constant 
     = 4 * T(N/4) + constant     ( 2 * constant = another constant )  
     = 8 * T(N/8) + constant  
     ... 
     = N * T(N/N) + constant  
     = N + constant  
     = O(N)



8) 

int j = 0; 
        for(int i = 0; i < n; ++i) { 
            while(j < n && arr[i] < arr[j]) { 
                j++; 
            } 
        }

Ans:
In the first look, the time complexity seems to be O(n^2) due to two loops.

However, note that the variable j is not initialized for each value of variable i.

Note that the variable j is not initialized for each value of variable i. 
Hence, the inner j++ will be executed at most n times. 
The i loop also runs n times. 
So, the whole thing runs for O(n) times.

Still not convinced ?

Lets assume the array passed has its element in decreasing order. We will just dry run through the code :


Iteration 1 : i = 0, j = 0. arr[0] < arr[0] is false. So, the inner while loop breaks. 
Iteration 2: i =1, j = 0. arr[1] < arr[0] is true. j becomes 1. 
Iteration 3 : i = 1, j = 1. Condition false. We break. Note that j will remain 1 and is not reset b
ack to 0. 
Iteration 4 : i = 2, j = 1. arr[2] < arr[1]. True. j = 2. 
Iteration 5 : i = 2, j = 2. Condition false. Break. 
Iteration 6 : i = 3, j = 2. arr[3] < arr[2]. True. j = 3. 
Iteration 7 : i = 3, j = 3. Condition false. Break. 


As you can see, the inner while loop only runs once in this case. 
So, total iterations is 2 * N.

Ans: O(N)