Precise Θ notation bound for the running time as a function

Question

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.

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) — willywonkadailyblah, Nov 15 '17 at 14:10

score 0 · Answer 1 · answered Dec 28 '17 at 21:02

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.

answered Dec 28 '17 at 21:02

Mohamed Ennahdi El Idrissi

2,873
2
18
32

Precise Θ notation bound for the running time as a function

1 Answers1