Searching is an operation which finds the location of a given element in a list. The search is said to be successful or unsuccessful depending on whether the element that is to be searched is found or not. Primarily we have two searching techniques named as Linear Search and Binary Search.
Sorting refers to the operation or technique of arranging and rearranging sets of data in some specific order. The term sorting came into picture, as humans realised the importance of searching quickly. The techniques of sorting can be divided into two categories named as Internal and External sorting.
Internal Sorting: If all the data that is to be sorted can be adjusted at a time in the main memory, the internal sorting method is being performed.
External Sorting: When the data that is to be sorted cannot be accommodated in the memory at the same time and some has to be kept in auxiliary memory such as hard disk, floppy disk, magnetic tapes etc, then external sorting methods are performed.
| SORTING ALGORITHM | TIME COMPLEXITY | ||
| Best Case | Average Case | Worst Case | |
| Bubble Sort | O(N) | O(N2) | O(N2) |
| Selection Sort | O(N2) | O(N2) | O(N2) |
| Insertion Sort | O(N) | O(N2) | O(N2) |
Lets develop good understanding of the searching and sorting techniques.
[Click the following links to watch the video]
- Understanding Linear Search [Read Text] [Download Text]
- Understanding Binary Search [Read text] [Download text]
- Understanding Selection Sort [Read Text] [Download text]
- Understanding Bubble Sort [Read Text] [Download text]
- Understanding Insertion Sort [Read Text] [Download text]
You are invited to raise queries by writing your question in the box given below
Expertvision 
Good morning professor
I wanted to ask question about finding running. When we have two seperate for loops, why its running time is O(n), instead of O(n+n)=O(2n)?
U1910133
Good morning!
These asymtotic notations are used to compare function with reference function(the one inside O). And when there is the n order polynom, then we should take the biggest n with power and we drop the coeficcient. That is because when n is arbitrary too large, then the difference between them(O(n) and O(2n)) is small, therefore you should drop the coefficient.
Understood, thank you.
U1910133
The n(variable) shows complexity whereas constants(like 1,2,3,4,5 …) just increase the time required per simplest step(like print(…)). And big O is all about complexity comparison.
Dear Saidakbar,
When we are finding the running time of program code, we are not actually concerned about the exact values. We rather try to define the behavior.
That’s why when you add them, They are still O(n) since they are both linear equations.
U1910256
Hello Saidakbar,
Actually you are right, the running time of that function is f(x) = 2n. However in terms of Big O notation we have to ignore the constant values because the main purpose of the Big O is to analyse the algorithm in a general fashion, that’s why O(n). Nowadays it doesn’t matter whether there are 10 or 20 iterations due to the advancement of computer technologies.
Actually it is 2n but look we use O(n) notation for very big inputs and this notation is not very precise. And for very big inputs 2*n and n is almost equal so we can omit numbers such as 2n 3n 3n/2 and so on.
For us it is more important to find the nature of the running time for a program or algorithm than its exact value.
Because they are two separate loops and dependent only on n, so the running time of both of them is n
U1910133
Good morning!
These asymtotic notations are used to compare function with reference function(the one inside O). And when there is the n order polynom, then we should take the biggest n with power and we drop the coeficcient. That is because when n is arbitrary too large, then the difference between them(O(n) and O(2n)) is small, therefore you should drop the coefficient.
Hello Saidakbar, the notation o compares only relative complexity( not absolute) I think this is the reason why O(n+n) is in fact the same as O(n).
Good daytime! An asymptotic notation describes the relationship between the function and it’s boundaries, so we’re mainly interested in a primary function, that is, the function where coefficients are 1 or 0 (ex: 2n^2 => n^2 or n+2=>n).
How to determine the average case complexity of an algorithm? Does average case depend on upper or lower bounds or it is determined independently?
Good day Mukhammadsaid
In order to find average case, firstly all possible inputs are taken and then computing time for all of the inputs will be calculated. after that you will sum all the calculated values and divide the sum by total number of inputs.
Average case depend on lower bounds
U1910133
There are two types of average case. First It is the average case for asymptotic notation. For example for linear search technique the average case of the worst case is n/2 therefore O(n) (case when the number searched is located in the mid of the list). Similarly average case for omega could be defined. Second there is average case notation that is theta. Theta defines the average case of program with the given input n. This happens when 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 (the point on the x axis after which the inequality holds). Or alternatively if o notation and omega notations are equal then they are equal to theta. Hope i could answer your question.
Why time complexity of binary search is Log of N? Why don’t we write it like Log base 2 of N.
Sorry my previous reply meant to be for person above you. For your question. When we write log we automatically assume that it has base 2.
Good morning, Bekzod. Big O notation represents the category of functions with certain complexities. We say that the time complexity of binary search is logarithmic, and it is enough for us to know. Basically, base of the logarithms are constant factors, and that’s why we don’t write them in big O.
We are not looking for the exact value, so even if the time complexity is “log base 8 of n” we just define it as “log n”. You can consider it as a standart form.
There are two types of average case. First It is the average case for asymptotic notation. For example for linear search technique the average case of the worst case is n/2 therefore O(n) (case when the number searched is located in the mid of the list). Similarly average case for omega could be defined. Second there is average case notation that is theta. Theta defines the average case of program with the given input n. This happens when 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0 (the point on the x axis after which the inequality holds). Or alternatively if o notation and omega notations are equal then they are equal to theta. Hope i could answer your question.
Good morning professor.
Foremost I am sorry for annoying at the weekend!
Can you explain me widely, what does actually iterative and recursive program differ from each other?
And which is more efficient in coding?
Hello. From higher perspective, iterative program works by executing one line after another from top to bottom whereas recurisve program works by calling itself and keeping mid-stages in stack(stages when some particular functions result is not defined yet). When it comes to the performance, most of the time performance of recursive program is worse than the iterative one. On the other hand sometimes implementing some task could be way easier and more intuitive using recursion(example fibonacci series).
An iterative algorithm is intended to repeat the same actions (set of instructions) using for, while and do … while loops. Recursive algorithm calls itself again and again till it fits the given condition.
Mostly, iterative algorithm is more efficient because it uses less time and space compared to recursive program. However, there are some cases in which recursion is preferred over iteration. Recursion is used when a particular action has to be repeatedly applied on the result of the previous action. Recursive programs usually provide smaller size of code.
An iterative program just repeats steps until a certain condition is satisfied while recursive program takes a big input and makes it smaller with every step until base case is satisfied. The both techniques are aimed for different cases. For example, for finding Fibonacci series or finding special folder in your computer memory, the recursive method will be more efficient
Dear Abdulmalik,
Let me answer your question in my words,
Basically, iteration means repetition. In programming, it is using loops like for loop or while loop.
Recursion is, on the other hand, calling the function within its body.
I think for small programs which do not take so much space in memory you can use both.
However, as your program becomes large, you should use iteration because recursion takes so much space in Stack(part of main memory where all functions are executed), and therefore it may slow down running time of your program noticeably.
Answer:
We use iterative program when we have loop condition and we use recursive program while we have function and it calls itself repeatedly.
Hello,
I wanna know whether it would be to say that Omega notation can comprise all functions of h(n) which are greater than or maybe equal to cg(n)for the values of n ≥ n0?
In a video about iterative algorithms, there was a loop which contained n = n/2, you considered it as notation O(log2 n), but in next loop there was k= k*2, why is it also O(log2 n)? Normally it should be O(log0.5 n), ain’t? I know that we could write such logarithm as -log2 n, in that case minus sign doesn’t matter? Thank you in advance.
Hi Akmal Ergashev, for the k = k*2 it’s a bit different.
“for(k=1; k<=n; k=k*2)" in this case k is increasing in range of 2^M, M=(1, 2, 3, …)
k = 1*2^0
k = 1*2^1
k = 1*2^2
……….
k = 1*2^M <= n "now we can use log rule for the both side. and in this case we can give log base 2"
log2(1) + M*log2(2) <= log2(n)
M<=log2(n)
Answer: O(log2(n))
The logic is the same, but syntax is different. “n=n/2” is in a “while” loop, we do it until (n>1), so we divide an input by 2 untill condition is true that mean our program will run “log2 n” times. “k=k*2” is in “for” loop and here we compare “k<=n", so it is the same as we divide an input by 2 untill condition is true ("n=n/2") instead of multiply "k"by two ("k=k*2").
Hello! I have a question regarding the selection sort. Let’s imagine the following implementation of the selection sort: instead of selecting the smallest element and putting it at the front, we instead select the largest element and put it at the end of the list. Does this change the algorithm’s efficiency?
Hi, in the first place it depends on the list, whether it is sorted or unsorted. If it is sorted list, then starts searching from 0th element and continues until the element is found. However, if it is a unsorted list, starts from oth element and continues until the very end of the element is reached. Guess, it will not change the effectiveness of an algorithm. Hope answered to your question approprately)
Doing this will not change the efficiency nor it will change adaptiveness. The algorithm still must iterate through all entries to find the largest element(in traditional case it find smallest). You are just reversing the logic of operations. In the analysis you still would get F(n) = (n-1)+(n-2)+(n-3)+…+3+2+1 = n(n-1)/2 = O(n^2).
Actually, this logic is used in buble sort algorithm. Using algorithm we compare pairs and we able to adjust the highest element at the highest position . But the bubble sort requires n-squared processing steps for every n number of elements to be sorted, similar to selection sort. That means, complexitywill stay as O(n^2).
I think no, you still have to find the largest element but instead of putting it to the left you just put it to the right. So, it`s like doing the same number of steps but just in different way (I can be wrong).
Still I did not quite get why we can not express the best case for linear search as O(n). We could say that it is n/16 if it is equal to 1 and n=16?
It is about how many times the loop runs. In this case it will be only O(1) as the best one. For other algorithms the constant for the best case may vary.
Hello. If we express the best case as O(n) that means the best case complexity depends on the size of the input. However that is not true for linear search imagine having a list of 10000000 elements and the element you are looking for is in the first place therefore you do not need to go through all 10000000 elements it is enough to make a single comparison. No matter how many elements you have in the list, as long as element you are looking for is in the first position(or any other exact position you know like 10 15 50 …) thecomplexity will be constant time theredore O(1).
Because a data you are looking for can be located at the first position. For example, imagine that you have a stack of books and you want to find “C++” book (just an example), so the best case for you is if this book is at the top of the stack ( 1st position).
Hello
Answer:
We can express best case of linear search as O(1). Because when we have only one comparison and worst case can be as O(n).
It is wrong to say that best case is omega(n) for linear search. In linear search best case requires only one comparison, based on your expression (n/16) i assume you mean that n represent number of comparison out of 16 elements.
so n is 1 as per your expression in best case but if you assume that n=16 then it refers to worst case, which indicate you did maximum comparison to get your answer.
If I have two separate cycle where first one’s time complexity is O(n) and second one’s is O(n^2) what will be time complexity of my program?
I assume you meant like two separate loops. In that case total complexity is n^2+n. Then we take only n with highest order therefore it will be O(n^2).
What is the main disadvantage of selection sort? And can we work with this algorithm when we use a large number of items in a list?
The primary disadvantage of selection sort is it’s poor efficiency. You are highly recommended to choose other soting algorithm when your input size is large.
What is the difference between buble sort and insertion sort, if complexity of algorithm in worst case is O(n^2), and in best case when it is sorted array O(n).
In insertion sort we should assume that first element is fixed, and we start comparing with second element(index 1)
Even though bubble sort and insertion sort belong to the same class of algorithms. Insertion sort runs faster than the bubble sort. The reason is bubble sort swaps all elements in unsorted part of list while insertion sort just puts next item in the sorted part. So the number of swaps in the case of insertion sort is smaller than in the case of bubble sort.