Big O notation

Hi i have exam on monday, so i will be asking for help in doing question in which i am clear
Big O notation








AND LAST ONE I DON"T EVEN KNOW ANSWER

Here's a quick guide (note that all answers are approximate, when we say O(logn) we don't necessarily mean LITTERALLY "logn"):
- O(n) represents complexity that is linearly related to n itself. For example, if you have n elements in a list and you have to delete them one by one. If you have n elements, you have n deletes. Or if you have to delete half the elements, then you have n/2 deletes. Regardless, the answer is expressed in terms of n to the first power times a constant (such as 2, 1/2, etc).
- O(logn) represents complexity that is approximately equal to n raised to a power less than one, or more accurately, a natural base (usually 2, in comp sci) raised to a power. This is basically saying that the time complexity is equal to some number exponentially less than n. For example, if you have a binary tree of data, finding an element of data does not require that you search every single element in the tree, you can use "divide and conquer" (if you will) to make your search faster and more direct. Thus, searching a 16 element database might only take 4 steps. If it were plain O(n) complexity, it would take about 8 on average. If you can express the time complexity as a function of n raised to a power less than 1, you probably have O(logn).

I can't recall just off hand exactily how to differenciate O(logn) from O(nlogn), though. IIRC, there isn't a perfect way to tell, you just have to estimate the time complexity and see if it appears to be somewhat linear (like O(n)), yet still logarithmic (O(logn)).

I hope some of that makes sense.

You might also be interested in reading this.

For first Ques: It is O(1) because it takes constant time to execute stmt. j = j/2.

and constant time complexity is O(1).

For secnd question it is O(n) becuse of for loop.
There are two operations : One is for loop and other is j = j/2 , but for loop time takes dominance so overall complexiy is O(n).

Q3.It is O(n) because each recursive call is taking n numbers into account. Had it been n/2 , complexity would have been O(logn).

Note that in the question Q3, value of n decreases constantly in each recursive call.


For Q4, quicksort takes variable time depending on nature of input being supplied.If it is presorted and you have to sort in reverse order , complexity is O(nlogn) . If it is sorted and you have to sort in same order , complexity is O(n^2).

For random ordered input complexity will again be O(nlogn).
you need to follow Quicksort algo.

One more point, it also depends on choice of your pivot.For example if you take median as pivot , quicksort is fastest.
If you take pivot as random , speed decreases by constant amount. and if you take extremes as pivots , speed is slowest by constant time.

Why? becuse if extremes are chosen as pivot, there is chance that one sub-portion has zero elements, becuse of which you have to start again.This ain't the case with pivot as median.

Last problem appears to be a O(logn) problem because recurrance equation is

T(n) = { O(1) , if n < 1
{ O(1) + 2T(n/2) , n > 1.