Everyone is a coder—until an interviewer asks about the time and space complexity of your program.

Time : what's a clock read

No this is not a definition of time complexity in computer science.

Amount of time taken by an algorithm is called it's time complexity. But how we measure the it actually. Is someone took a clock and check the second of CPU . No we use some mathematical things called asymptotic notation to determine the time and space. We have 3 notation omega,theta and big O these three can calculate the time

Let's discuss and understand one by one.

Big (O)

It describes the worst-case scenario in terms of time or space complexity. The upper bound of the complexity.

Big O(n)

#include <bits/stdc++.h>
using namespace std;

// Function to find an element in an array
bool findElement(int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return true;
        }
    }
    return false;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5}; // Example array
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate size of the array
    int key = 3; // Element to search for

    if (findElement(arr, n, key)) {
        cout << "Element Found" << endl;
    } else {
        cout << "Element Not Found" << endl;
    }

    return 0;
}

So, what does O(n) actually mean? It indicates that, in the worst case, you might have to iterate through the array up to n times to get the result. However, it may not always take n iterations. The key point to remember is that it will not take more than n iterations to find the solution.

• The for loop runs from i = 0 to i = n - 1, iterating over the array.

• In the worst-case scenario, the loop will execute nnn times (if the key is not in the array).

• In the best-case scenario, the loop will execute 1 time (if the key is found at the first position).

  Time complexity of this function:

  • Best case: O(1)

  • Worst case: O(n)

Big O(log n)

#include <bits/stdc++.h>
using namespace std;

// Function for binary search
int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;

        // Check if the element is present at mid
        if (arr[mid] == x)
            return mid;

        // If the element is smaller, search the left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);

        // Otherwise, search the right subarray
        return binarySearch(arr, mid + 1, r, x);
    }

    // Element is not present
    return -1;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5}; // Example array
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate size of the array
    int x = 3; // Element to search for

    int ans = binarySearch(arr, 0, n - 1, x); // Corrected bounds
    if (ans != -1) {
        cout << "Element found at index " << ans << endl;
    } else {
        cout << "Element is not available" << endl;
    }

    return 0;
}

depending on the itration it will find the complexity..

• Binary search works by dividing the array into two halves at each step.

• Recursive Call Pattern:

  • It checks the middle element.

  • If the middle element matches the target, it returns.

  • Otherwise, it recurses into one-half of the array, effectively reducing the size by half at each step.

The number of elements processed at each level forms a geometric progression:

n,n/​2,n/4​,…,1

The total number of steps required to reach a single element is:

log⁡2(n)\

Time Complexity: O(log⁡n).

How to Determine ?

As of now, let's calculate time — the amount of time taken by an algorithm to complete.

But there are several algorithms that have fixed time complexities, such as Binary Search, which has log(n) time complexity.

So first, you should learn or memorize the time complexity of some common algorithms.
If you find a loop which is runing on N times n stands for any natural number.
not every time N sometimes input like 26 times 10 times so the complexity will be O of (26) or of(10) but generally inputs stand for N natural numbers so we called as N time.

void display(vector<int>nums){

  int n = nums.size(); 
  for(int i =0;i<n;i++){
      cout<<nums[i]<<" ";
  }
}

Time-Complexity O(n);

Now if i make a nested loop or a another loop.

void display(vector<int>nums){

  int n = nums.size(); 
  for(int i =0;i<n;i++){
      cout<<nums[i]<<" ";
  }

 for(int i =0;i<n;i++){
      cout<<nums[i]<<" ";
  }
}

In the case if we calculate it will be like.
T(n) = O(n) + O(n)

T(n) = O(2n)

we generally reduce the constant terms.
final will be
T(n) = 0(n)

Now if we nest loop it will be multiply like.

void display(vector<int>nums){

  int n = nums.size(); 
  for(int i = 0;i<n;i++){ -----------------O(n)
      for(int j =0;j<n;j++){-----------------O(n)
         cout<<nums[i]+nums[j];
     }
  }
}

In the case if we calculate it will be like.
T(n) = O(n) * O(n)

T(n) = O(n^2)
You often hird that T(n) = O(n^2) is worst time complexity.
So, these are some simple ways to determine the time complexity.

But, but the question is: how can you determine when a program is using an algorithm like this?

void display(vector<int>nums){

  int n = nums.size();
  sort(nums.begin(),nums.end()); 
  for(int i =0;i<n;i++){
      cout<<nums[i]<<" ";
  }
}

In this program, you can clearly see that first we are sorting and then looping.

So, the time complexity will be:

T(n)=nlog⁡(n)+O(n)T(n) = n \log(n) + O(n)T(n)=nlog(n)+O(n)

Here, nlog⁡(n)n \log(n)nlog(n) stands for sorting because most of the time sorting functions use Quick Sort internally.

So, the overall time complexity will be:

T(n)=nlog⁡(n)T(n) = n \log(n)T(n)=nlog(n)

You need to think about it in a simple way, like polynomial mathematics.

We ignore constant terms and focus on the largest-growing part.

Please give your feedback and valuable suggestions for more clarity on this topic.
I know I have not included many things yet. Open for collaboration. 🤞