0

I'm studying for an exam, and i've come across the following question:

Provide a precise (Θ notation) bound for the running time as a function of n for the following function

for i = 1 to n {
    j = i
    while j < n {
        j = j + 4
    }
}

I believe the answer would be O(n^2), although I'm certainly an amateur at the subject but m reasoning is the initial loop takes O(n) and the inner loop takes O(n/4) resulting in O(n^2/4). as O(n^2) is dominating it simplifies to O(n^2).

Any clarification would be appreciated.

reemq8
  • 9
  • 1
  • 4
  • something like https://stackoverflow.com/questions/44085863/what-is-the-time-complexity-of-the-following-algorithm/44086434#44086434 – Matt Timmermans Nov 15 '17 at 05:07
  • Your reasoning is not right for inner loop but it's complexity is quadratic. The inner loop run for N times then (N-1) then (N-2) etc so you get N*N => N^2 – Luai Ghunim Nov 15 '17 at 09:47
  • The inner loop is O([n-i]/4), because i can take values up to n, so cannot be ignored. But the final result would still be O(n^2) – meowgoesthedog Nov 15 '17 at 14:10
  • Ahh okay! thank you! that made it a lot clearer. – reemq8 Nov 16 '17 at 00:21

1 Answers1

0

If you proceed using Sigma notation, and obtain T(n) equals something, then you get Big Theta.

If T(n) is less or equal, then it's Big O.

If T(n) is greater or equal, then it's Big Omega.

enter image description here

Mohamed Ennahdi El Idrissi
  • 2,931
  • 2
  • 19
  • 32