Space and Time Complexity in Detail || Java + DSA Course || Blog 13

Every computer has a different processor, so algorithm can take different time to execute.

So, Time complexity doesn't talk about the time taken by the algorithm. Instead, it considers how many times each statement executes.

For a quick overview, we will be looking at:

• What is Time complexity?
• Solving Time complexity
• Big O Notation
• Big Omega Notation
• Theta Notation
  
• Little O Notation
• Little Omega Notation
• Space Complexity

What is Time Complexity?

Time Complexity tells us how the time is going to grow depending on its input so we can estimate value at any point.

This is the Graph of Different Time complexities:

Here, O(1) is constant time complexity. It means your time will remain constant at every input length.

O(log n) is the time complexity used by Binary search(algorithm used to search a value in a sorted array). It starts to curve at a certain point. The more the input, the less time Taken.

O(n) is the time complexity used by Linear search(algorithm used to search a value in a sorted array). As you can see, it is a straight line. The more input length, more is the time.

O(n^2) is the time complexity used by Selection sort(algorithm which sorts an element by picking minimum element every time and putting it in place). The time increases on a huge scale when the input increases.

So, we can say that the good one here, is O(1)(constant).

To categorize it through time, it is;

O(1) <  O(log n) < O(n) < O(n^2)

Solving Time Complexity   

Lets say we built a website, if we have 10 to 15 people on our website, nothing is going to happen to website.

But lets say there was 100000 traffic on it, there is a major possibility that it would crash.

 

Having 10 people on website isn't that big a deal than 100000.

So, what important is we should always look for worst case and huge data. ......(1)

 

As i said earlier, time changes from computer to computer. Important is the graph. 

The Line. So we should ignore the Constants.(ex: 2n. 2 isn't necessary) .......((2)

 

Lets say, we have a complexity of O(n + log(n)) and n = 1million

so, O(1million + 6sec).

Here, 6 seconds is very less compared to 1million. 

Always ignore the less dominating term.    .......(3)

 

Lets try to solve a question

O(5n^3 + 2n^2 +4n + 10)

O(n^3  + n^2 + n)................from (2)

O(n^3)...........from (3)

So, the Answer is O(n^3)

 

Big O Notation(O)

The term we were using earlier(O(n)) is called Big O Notation. Its also called upper bound. It stands for the Worst case scenario. It says that whatever the input length is, time will not exceed from O(..). 

In Mathematics, its writtern as f(n) / g(n) < infinity

f(n) is the actual equation.(ex:  O(5n^3 +4n + 10))

g(n) is the equation we got. ( O(n^3))

 

Lets say n = infinity

Here, we can say 5 (constant) is surely less than infinity.

 

 

Big Omega Notation(Ω)

Big Omega Notation is also called Lower Bound. It is the Best case scenario. It says that whatever the input length is, time will not fall behind from Ω (..). 

It says, f(n) / g(n) > zero

 

Theta Notation(θ)

Theta notation is nothing using big o notation and big omega notation.

It says, 

0 < f(n) / g(n) < infinity

Little O Notation

Little O Notation is also called upper bound but it is a loose/strict case .

It says, f(n) / g(n) <= infinity

 

Little Omega Notation

 

Little Omega Notation is also called lower bound but it is a loose/strict case .

it says, 0 <= f(n) / g(n)

Space Complexity 

Space complexity is nothing but the input length and constants used in algorithm. It includes both Auxiliary space and space used by input. 

 

This was all about Time and Space complexity which we will be using in Data Structures and algorithms.

 __________________________________________________________________________________

Checkout:https://javaanddsa.blogspot.com/

Did you like our blog 13??

Tell us in the comment section