Background introduction

Here are some problems related to Big-O notation.

From now on, I will try to write blogs in English for my English interview.

But below the English descriptions there will be some translations in Chinese, so you guys who don't know English well can still read my article.

中文：

這是一些關于算法分析的題目。

我最近要開始嘗試用英語寫博客了，但是我會附上中文翻譯在下面。

Upper bound or Lower bound?

Question:

Suppose your friend discovers a new algorithm and in his excitement tells you that his algorithm has a lower bound of O(n2). Can you explain why your friend's statement makes no sense?

Answer:

Let me explain the definition of the two bounds.

The lower bound is the best an algorithm can perform. Oppositely,the upper bound is the worst an algorithm can perform.

And Big O notation cares about the upper bound but is silent about the lower bound.

We can not say in the best case the running time complexity is quadratic or better,may be in linear or constant.

Hence,It makes no sense and it's not logical.

中文解讀：

大O表示法關注的是一個最差的情況，但是下界意思是最佳情況，所以下界是O(n^2)這種表述的意思是 在最佳情況下，算法的時間復雜度最差是n^2，這種說法是不合邏輯的。

Formal Definition of Big O

Question:

Does O(2^2n) equal O(2^n) ?

Answer：

First of all, O(g(n)) means a set of functions.

if O(2^2n) equals O(2^n) , it means that two statements are ture at the same time.

• we can find any functions which belongs to O(2^2n) must belongs to O(2^n)
• we can find any functions which belongs to O(2^n) must belongs to O(2^2n)

Let's test the f(n) = 2^2n

if 2^2n = O(2^n) , so the inequality 0 <= 2^2n <= c2^n holds when c is positive and n is greater than n0

let's divide both sides by 2^n, and we can see

0 <= 2^n <= c ，when c is fix, we can find a n' which makes the inequality false.

So O(2^2n) is not equal to O(2^n)

中文解讀：

首先翻譯一下題目，能想得到若題目條件成立，則必須同時滿足兩個條件：

• 任何屬于2^2n函數集合的函數也都屬于2 ^ n集合
• 任何屬于2^n函數集合的函數也都屬于2 ^ 2n集合

這兩個集合就一模一樣了。

用反證法證明，若2^2n屬于O(2 ^n)，最后推出矛盾結果，所以并不相等。

M % N means?

Determine the time complexity for the following snippet of code

    void complexMethod(int n, int m) {

       for (int j = 0; j < n; j++) {   
          for (int i = 0; i < m % n; i++) {
              System.out.println("")
          } 
       }
    }

Answer：

m%n is the key to solve the problem.

if m equals n, m%n equals 0 and the inner loop will not run. The complexity is O(n)

if m is less than n ,m%n equals m and the complexity is O(m*n).

The last case is when m is greater than n, m%n equals value ranging from 1 to n-1, So the complexity will in the worse case be O(n^2)

Hence, the complexity would be O(n^2)

中文解讀：

內層循環的余數需要分為三種情況討論，最差的情況是O(n^2),所以整個算法的時間復雜度是O(n ^2)