**Introduction**

**In computer science, the time complexity of an algorithm quantifies **

**the amount of time taken by an algorithm to run as a function of the **

**length of the string representing the input.**

**2. Big O notation**

**The time complexity of an algorithm is commonly expressed using big O**

** notation, which excludes coefficients and lower order terms. When **

**expressed this way, the time complexity is said to be described **

**asymptotically, i.e., as the input size goes to infinity.**

**For example, if the time required by an algorithm on all inputs of size n is at most 5n**

**3**

**+ 3n, the asymptotic time complexity is O(n**

**3**

**). More on that later.**

**Few more Examples:**

**1 = O(n)****n = O(n2)****log(n) = O(n)****2 n + 1 = O(n)**

**1) O(1): Time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function.**

// set of non-recursive and non-loop statements

**For example swap() function has O(1) time complexity.**

** A loop or recursion that runs a constant number of times is also considered as O(1). For example the following loop is O(1).**

// Here c is a constant for (int i = 1; i <= c; i++) { // some O(1) expressions }

**Examples:**

**array: accessing any element****fixed-size stack: push and pop methods****fixed-size queue: enqueue and dequeue methods**

**2) O(n): Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount. For example following functions have O(n) time complexity.**

// Here c is a positive integer constant for (int i = 1; i <= n; i += c) { // some O(1) expressions } for (int i = n; i > 0; i -= c) { // some O(1) expressions }

**Consider the following examples, below I am linearly searching for an element, this has a time complexity of O(n).**

**int find = 66;****var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };****for (int i = 0; i < numbers.Length – 1; i++)****{****if(find == numbers[i])****{****return;****}****}**

**More Examples:**

**Array: Linear Search, Traversing, Find minimum etc****ArrayList: contains method****Queue: contains method**

**3) O(n ^{c}): Time complexity of nested loops is equal to the number of times the innermost statement is executed. For example the following sample loops have O(n^{2}) time complexity**

for (int i = 1; i <=n; i += c) { for (int j = 1; j <=n; j += c) { // some O(1) expressions } } for (int i = n; i > 0; i += c) { for (int j = i+1; j <=n; j += c) { // some O(1) expressions }

**For example Selection sort and Insertion Sort have O(n ^{2}) time complexity.**

**4) O(Logn) Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount.**

for (int i = 1; i <=n; i *= c) { // some O(1) expressions } for (int i = n; i > 0; i /= c) { // some O(1) expressions }

**For example Binary Search(refer iterative implementation) has O(Logn) time complexity.**

** 5) O(LogLogn) Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased exponentially by a constant amount.**

// Here c is a constant greater than 1 for (int i = 2; i <=n; i = pow(i, c)) { // some O(1) expressions } //Here fun is sqrt or cuberoot or any other constant root for (int i = n; i > 0; i = fun(i)) { // some O(1) expressions }

**How to combine time complexities of consecutive loops?**

** When there are consecutive loops, we calculate time complexity as sum of time complexities of individual loops.**

for (int i = 1; i <=m; i += c) { // some O(1) expressions } for (int i = 1; i <=n; i += c) { // some O(1) expressions } Time complexity of above code is O(m) + O(n) which is O(m+n) If m == n, the time complexity becomes O(2n) which is O(n).