What is Algorithm, Time & Space Complexity

Definition : Algorithm is finite set of instruction that solve a given problem and also help to solve similar kind of problems.

Isn’t it sounds very familiar to the definition of Program ?

Yes, but actually No as they are not the same.

Main Difference is that we write program in a programming language like java, python , ruby etc. and it starts when our design is ready to get implemented .

Let’s go back to our first line where I mentioned finite which means that Algorithm terminates with the answer or just by informing that there is no answer exists.

Algorithm is not a single step task , it needs a lot of analysis then validating those analysis with proofs to be sure that the provided solution is the best solution .

Question : How, I will be sure that its the best solution for the given problem 🤔 🧐?

Answer : For this, we need to check its TIME & SPACE Complexity , network , power (power consumption by device) .

Different performance measures are also taken into consideration :

• Worst Case
• Best case
• Data - specific case

TIME Complexity : It is the amount of time required by the algorithm to execute for completion.

Time Complexity order is as follow, lowest shows min time required.
1<log n < √n< n < n log n < n² < n³ …< n^n

SPACE Complexity : It is the amount of memory needed by the algorithm in its life cycle . E.g. Space needed to store variables or certain data.

Complexity (Time or Space)is defined in terms of : BigO (O) , theta (⍬), Omega (Ω)

• Worst case or upper bound: O(..) — f(n)= O(g(n)) if f(n) ≤ c* g(n)
• Best case or lower bound: Ω(..) — f(n)= Ω(g(n)) if f(n) ≥ c* g(n)
• Composite bound: ⍬(..) — f(n)= ⍬(g(n)) if c1* g(n) ≤ f(n) ≤ c2* g(n)
• Average or typical case notation is less formal — We generally say “average case is O(n)” thats the reason you might have heard most of the time in term of BigO.

let take few example of Time Complexity

(Note: I will explain how to calculate time and space complexity in different blog)