thnx for explaining it in such a simple way...i understood it in 5 minutes..

Hi Friends,

I am doing Msc-IT from KSOU.
I Have exams on 28th iam not understanding Complexity concept and Big O notation(Best, average and worst case) need help from you all.

Manju

oops.............

@ Rashakil Fol and @ Narue : you both clearly have super strong fundamentals !! thanks a lot for giving such a beautiful explanation of complexity that i could have never found out in any algo book !! Looking forward to more brainstorming sessions !! thnx a lot !! best wishes !!

Is O(1)run time complexity is low? and wat exactly it mean?

I have big problem with Alogorithm can someone help me............

Question..Find the Thetha Notation for the following.

b). t(n) = (n + 1 )(n + 3)/(n + 2)

Theta means a "tight" bound in the sense that you bound something above and below by a growth order.

Basically, if you can find a growth order such that t(n) is in big-Oh of the order, as well as in big-Omega of the order, then t(n) is by definition in Theta of that order.

Hint: Let n -> infinity, as though you were taking a limit. What does t(n) look like in the limit of large n?

Hint 2: If you want to go beyond that, take your answer from the first hint and prove it is correct by finding constants a, b, and m such that a*f(n) <= t(n) <= b*f(n) for all n >= m. You don't have to find tight a and b... just make them positive and you're good to go.

a:=0
for i:=4 to n then
{
a=i*i;
}
return(a)

what is the freguency count of this algo ??
explain plz...,

a:=0
for i:=4 to n then
{
a=i*i;
}
return(a)

what is the freguency count of this algo ??
explain plz...,

Can you describe an algorithm that is O(nm)?

I'm guessing it would be something like traversing a two-dimensional array. The two loops needed to do that is throwing me off however. It's making me think that it could be O(n^2).

>Can you describe an algorithm that is O(nm)?
>I'm guessing it would be something like traversing a two-dimensional array.
Good guess. That's an excellent way of describing O(nm).

>The two loops needed to do that is throwing me off however.
>It's making me think that it could be O(n^2).
If it helps, you can think of O(n^2) as O(nn), redundant as it may be. The difference here is that with O(nm), n and m don't have to be the same value. They can be, and in that case the time complexity is indeed quadratic.

>The two loops needed to do that is throwing me off however. >It's making me think that it could be O(n^2). If it helps, you can think of O(n^2) as O(nn), redundant as it may be. The difference here is that with O(nm), n and m don't have to be the same value. They can be, and in that case the time complexity is indeed quadratic.

Thanks! Good way to put it. I can see it being quadratic if the matrix contains the same amount for each dimension.

...

Given a 2D array which is sorted in non-decreasing order(increasing). what will be the expected time complexity to find an element in that 2D array?

Gee, why don't you figure this out for yourself?

Picking up from the 2D array SEARCH (not sorting), and assuming it to be n * n.
Just want to check if I got it right (intuitively):
- the worst case is O(n^2) - potentially last entry
- best case is O(1) - potentially first entry
- average case? if I should imagine an average, I would expect the searches to be distributed in the middle, so n/2 * n/2, which would be still O(n^2)

Is this correct?

Sorry, I cannot find an EDIT button...

What I meant was: from 2 posts before "Given a 2D array which is sorted in non-decreasing order(increasing). what will be the expected time complexity to find an element in that 2D array?"
Therefore my question quoted here:
Picking up from the 2D array SEARCH (not sorting), and assuming it to be n * n.
Just want to check if I got it right (intuitively):
- the worst case is O(n^2) - potentially last entry
- best case is O(1) - potentially first entry
- average case? if I should imagine an average, I would expect the searches to be distributed in the middle, so n/2 * n/2, which would be still O(n^2)

Is this correct?

Edit: curiously, the EDIT button is present in this post, but not in my previous.

actually
for each loop we can assume it is in the order of n or {0(n)}

4+ months old thread from the previous reply post (above mine)...

By the way, non-sorted 2D array with nxm will have O(nxm) because you have no uniform rule to search, so you would try to look through the whole array. Average case to me is still O(nxm)...

For a sorted 2D array, it will easily become O(logn) regardless the m and n values. Or the exact time would be log2.

2 programs a and b that have performance as o(log n) and o(n),if each program requires 10 sec to solve a problem of size 1000,what is the time required for each to double.